После пяти лет пребывания у власти, последовательных усилий по централизации государства, концентрации реальной власти в руках господаря, Штефан III подумывает о первых действиях по интеграции страны. Готовится к «справедливой войне» (bellum justum), по возвращению Молдове некоторых важных экономических и военных центров. Год спустя, после экспедиции в Трансильванию (против укрывателей претендента Петру Арона), Штефан пытается (22.06.1462 г.) освободить крепость и порт на Дунае – Килию, захваченную венграми. Кампания не удалась. Штефан был ранен (в ногу). От этого недуга он будет страдать всю жизнь. Но, повторим, «там, где его побеждали другие, не терял надежды (...) что поднимется над победителями». Спустя несколько лет, в конце января 1465 г., Штефан III изгоняет венгров из Килии, назначает пыркэлабом крепости и ее окрестностей Исаю, своего шурина.

В отношениях между Молдовой и Венгрией различаются два периода: до битвы у Баи (1467 г.) и после этого кровавого столкновения. Во главе венгерского королевства в те годы стоял Матей Корвин – сын Янку Хунедоара, трансильванского молдо-валаха , выдающегося венгерского полководца с популярностью и полномочиями короля. Корвин, был достойным сыном своего отца, став одним из самых искусных дипломатов и военных стратегов своего времени. И уже в первые годы правления этого короля, храброго и гордого воина, Штефан III посягнул на то, что мадьяры считали им принадлежащим. Разумеется, Матей Корвин понимал, что Молдова – это преграда на пути османской экспансии, которая угрожала южным пределам Трансильвании.

Из этих соображений Венгрия была, в общем-то, заинтересована в самостоятельности Молдовы, в стабильных с ней отношениях, оккупируя при этом молдавский порт и крепость Килию. Сознавая коварное отношение польских магнатов, Штефан III, в свою очередь, также был заинтересован в том, чтобы не портить отношения с Венгрией. Но не ценою уступки Килии или позволения Венгрии стимулировать претензии Петру Арона на молдавский престол. Так оправдывались вторжения молдавских отрядов в Трансильванию, две осады (1462 и 1465 гг.), в результате которых Килия была освобождена и возвращена Молдове. Но и Матей Корвин был не менее амбициозен. Он тщательно подготовился к кампании по наказанию Молдовы и ее господаря.

Битва у Баи. Венгерская армия (около 40 000), во главе с самим Матеем Корвиным, отправляется (ноябрь 1467 г.) из Брашова к Молдове. Экспедиция имела четкое задание – наказание молдаванина Штефана III и Молдовы. Венгерский суверен одновременно хотел покорить Молдавскую Страну и посадить на ее трон нового господаря. После некоторых столкновений у перевала Ойтуз молдавские отряды отходят, изматывая частыми налетами противника. Тот захватывает и поджигает молдавские города Тротуш, Бакэу, Роман, Нямц. Направляясь к Сучаве, Матей Корвин и его войска остановились в Бае, бывшей столице Молдовы. Здесь Штефан III подготовился к решительному бою. В ночь с 14 на 15 декабря 1467 г. молдавское войско (около 12 000) окружило Баю, подожгло город, атаковало противника и в кровавой схватке разбило его. Согласно плану битвы, составленному Штефаном III, все корпуса молдавской армии должны были атаковать противника одновременно и сконцентрированно. Однако корпус под командованием ворника Краснэша не вступил в бой. Этот постыдной поступок, равный предательству, позволил части венгерской армии и тяжело раненному венгерскому королю бежать.

Преследуемые молдавскими воинами, остатки венгерской армии отступили в Трансильванию. Однако Штефан III не довольствовался этим. Решив возместить ущерб, причиненный его стране венгерскими интервентами, и с целью наказания враждебного отношения секуев к молдавскому господарю, молдавское войско под командованием второго спатаря, Филиппа Попа, вторгается в Трансильванию (1469 г.) и наказывает секуев. Кампания Матея Корвина в Молдову, в которой горделивый король и его армия потерпели суровое поражение, оказалась последней попыткой венгров покорить Страну Молдавскую. Блестящая победа молдавской армии под командованием Штефана III стала важным актом утверждения в европейском контексте авторитета Молдовы и ее господаря.

В последующих десятилетиях молдавско-венгерские связи, отношения между молдаванином Штефаном III и венгром Матеем Корвиным будут строиться, исходя уже из других интересов, развиваясь в направлении сотрудничества перед лицом общей угрозы. Желая поддержать дружбу и взаимопонимание с соседями, Штефан III предложил заключить (при посредничестве польского короля) стабильный мир с Матеем Корвиным, от которого молдавский суверен требовал возмещения ущерба, нанесенного его стране в 1467 г. Но стороны не смогли договориться. Обе страны предприняли значительные шаги по улучшению молдавско-венгерских отношений. Королевским актом от 20.01.1473 г. М. Корвин дает гарантии молдавским торговцам вести дела в городах Трансильвании: Бистрице, Брашове, Клуже, Сибиу. В свою очередь Штефан III еще раньше подписал (3.04.1472 г.) торговую привилегию брашовянам. Салвкондуктом (документ для свободного передвижения) от 10.07.1475 г., подписанном Штефаном III, все венгерские купцы «свободны приходить добровольно и без задержки со всем своим товаром, продавать и покупать свободно и добровольно, без преград и без ущерба, будь то в мирное время или в мятежное». 12.07.1475 г. заключается молдавско-венгерский договор, где обе стороны выказывают озабоченность в связи с тесным военным сотрудничеством, фактически, с объединением между Валахией и Оттоманской Империей. Подписанный в Яссах договор был направлен прежде всего против оттоманов. Штефан III признал, из стратегических соображений, сюзеренитет венгерского короля, обязуясь оказать ему помощь против любого врага, «кроме короля Польши... с которым наши предшественники имели мир и договоры». Матей Корвин обещал не укрывать в своей стране ни одного врага Молдовы. В то же время дипломом, подписанным в Буде (15.08.1475 г.), М. Корвин обязывался помочь Штефану III в его битвах с оттоманами. Переговоры и подписание молдавско-венгерского договора в Яссах (12.07.1475 г.), его статьи отражают в большой мере суть внешней политики Штефана III Великого, продиктованной географическим положением, геополитической конъюнктурой, реальными возможностями страны. Управляя страной, которая имела на западе и северо-востоке сильных соседей, не скрывающих своих территориальных притязаний, находясь под постоянной угрозой, атакуемый почти ежегодно с юго-запада валахами и османами, а с юго-востока – татарами, Штефан III Великий должен был маневрировать очень внимательно, дипломатически, тонко и своевременно. Поэтому, хотя побил Матея Корвина у Баи и предпринимал походы в пределы Венгрии, Штефан признает его сюзеренитет, находясь в условиях, когда Молдова была под сюзеренитетом Польши на основе договоренности от 4.04.1457 г., подтвержденной Молдавско-польским договором от 18.07.1468 г. Подобным двойным вассалитетом Штефан III добивался исключения любых угроз своему трону и достижения стабильности, пусть и шаткой, на северо-восточном и северо-западном направлениях. Молдова признанием двойного сюзеренитета Польши и Венгрии одновременно находилась как бы под защитой обеих, потому что претензии и Польши, и Венгрии взаимоисключались.

Таким образом, искусной дипломатией Штефана III Великого Молдова к 1475 г., являясь де-юре под двойным вассалитетом, де-факто же была полностью самостоятельной. Что действительность была именно такой, убеждает документ, подписанный летом 1489 г., которым М. Корвин давал в собственность Молдове крепости Чичеу и Четатя де Балтэ в Трансильвании с их владениями. Эти крепости, в которые Штефан III назначил молдавских пыркэлабов, были дарованы господарю Молдовы в качестве компенсации за потерю Килии и Четатя Албэ, захваченных османами и валахами в 1484 г. Эта концессия подчеркивает альянс Венгрии и Молдовы против османов и, в некоторой степени, против Польши. Взаимные связи между Молдовой и Венгрией укрепляются и родственными отношениями – женитьбой Александра, старшего сына Штефана III, на дочери воеводы Трансильвании Бартоломеу Драгффи. Признаки уважительного отношения М. Корвина к Штефану III выявились и при налаживании отношений – посредством венгерского двора – Молдовы с папской курией, которая оказала определенную помощь молдаванам летом 1476 г... Или другой пример: Бартоломеу Драгффи, посланец венгерского короля, был посредником при улаживании молдавско-польского конфликта в Сучаве. Таким образом, исходившие вначале из давнего своего соперничества, достигшего апогея в кровавой битве у Баи, отношения между Молдовой и Венгрией, благодаря стратегическому политическому видению и дипломатическому искусству своих суверенов – молдаванина Штефана III Великого и венгра Матея Корвина – в последней четверти XV в. развивались на принципах полного равенства, взаимного уважения и взаимной помощи. То, что не всегда можно было сказать о других соседях Молдовы.