1457年四月下旬，斯特凡率领一千瓦拉几亚骑兵和两千德意志佣兵从保加利亚出发北上摩尔达维亚。
流亡公子的归来立刻受到了摩尔达维亚贵族们的热切欢迎。
支持斯特凡的贵族和民众们纷纷加入他的军队，很快斯特凡手下就聚集了将近一万人马。
斯特凡的大军并未受到有力的抵抗，所到之处城堡和城镇望风而降，彼得大公屈辱的统治使他彻底失去了民心，人们期盼一位更加强硬的君主。
不久，斯特凡率军进抵罗曼城，摩尔达维亚南部的所有地区都已被他征服。
彼得大公的部队终于集结完毕，他率领不足五千兵马在城外的锡雷特河西岸扎营，与斯特凡隔河对峙。
同时，彼得的信使正星夜兼程赶往克拉科夫，请求波兰国王瓦迪斯瓦夫三世的援助。
只不过他已经等不到波兰王收到他的求援信带兵来拯救他了。
斯特凡将沿途招募的大军驻扎在河岸边按兵不动，以此迷惑彼得。
他自己亲率从瓦拉几亚和保加利亚那里得到的精锐部队趁着夜色急行军从浅滩渡过锡雷特河。
这支部队渡河后只休整片刻，便追随斯特凡在第二天的清晨突袭了彼得大公的营地。
缺乏准备的摩尔达维亚军队被这闪电般迅猛的突袭打的丢盔弃甲，彼得大公本人只带着几名亲信趁乱逃亡波兰。
原本就没有多少抵抗意志的摩尔达维亚人立刻喜迎新王，斯特凡只用了不到一个月的时间就夺回了整个摩尔达维亚。
再次回到苏恰瓦(摩尔达维亚首都)后，斯特凡立刻展现出自己卓越的能力，开始整顿这个残破不堪的国家。
第一步，斯特凡颁布赦令，免除彼得追随者的一切罪责，召回由于政权更迭而逃亡出国的贵族。
随后，斯特凡重建了摩尔达维亚的政府，仿照奥地利的体制建立了摩尔达维亚枢密院治理公国，同时宣布恢复他的祖父老亚历山德鲁时期使用的东罗马律法，确立法纪，依法治国，迅速有效地重建公共秩序。
最后也是最重要的一步，斯特凡召集了摩尔达维亚境内的每一名士兵，收编俘虏，处决触犯军纪，骚扰民众的兵痞，剔除掉军队中滥竽充数的老弱病残之后，保留下一支人数在五千左右的精兵。
剩下的士兵被强制遣散，有些归乡务农，外国的则被礼送出境，而那些没有接受斯特凡征召却游荡在公国境内的士兵，一律被视为强盗，斯特凡派出手下的瓦拉几亚骑兵在公国内游荡，肃清每一个城镇，每一个村庄附近的所有强盗。
这般雷厉风行的手段使得整个摩尔达维亚在极短的时间内安定下来，国内的秩序之稳定甚至远远超过了彼得统治的时期。
腓特烈接二连三来信催促斯特凡收复摩尔达维亚西部边境被波兰人侵占的城堡要塞。
摩尔达维亚国内也有许多贵族希望斯特凡能够对波兰人表现的强硬一些。
经过多方面的考量之后，刚安顿下来的斯特凡再次率军出征，很轻易就收复了霍亭堡等几个被波兰人侵占的边境城堡要塞。
随后，斯特凡率军越过国境线，进入波兰境内，开始攻击和劫掠波兰的边境城镇。
克拉科夫，波兰国王的宫廷里，瓦迪斯瓦夫三世看着手里的报告，还有跪在自己宫廷里哭诉的彼得大公，顿时一个头两个大。
在西边，条顿骑士团的军队与波兰王国的大军正隔着维斯瓦河对峙，此刻双方正处于一个微妙的休战期。
在东边，波兰人在摩尔达维亚的统治彻底被摧毁，斯特凡正率领一支实力强劲的军队扫荡波兰东部，瓦迪斯瓦夫三世心中烦躁不已。
他是有些担心，不过现阶段情况还没有太糟糕，就算条顿骑士团和摩尔达维亚捆在一起都打不过波兰。
问题在于他无法快速拿下实力强悍，堡垒林立的条顿骑士团，摩尔达维亚背后的黑手也令他忧心忡忡。
“陛下，我们应该召集议会商讨对策了。”