Несмотря на то, что Молдова актами, ранее подписанными, являлась будто бы под дланью Польши, Штефан в 1457 и 1458 гг. предпринимает жесткие вторжения в южные области Польши, стремясь схватить Петра Арона, убийцу его отца. Занятая конфликтом с тевтонами, Польша не ответила. Напротив. Согласилась и подписала молдавско-польский договор в Оверхелэуць (1459 г.), которым Штефан добился того, чего хотел. Более того, в результате договоренности в 1462 г., и годом позже, в 1463 г., крепость Хотин, уступленная ранее Петром Ароном Польше, возвращалась Молдове. Удовлетворяя претензии (скорее дипломатически- церемониальные) польского суверена, Штефан подписывает 28.07.1468 г. новый Молдавско-польский договор, которым господарь Молдовы подтверждает ранее установленные двусторонние отношения. Польский король обязуется не укрывать ни одного претендента на трон Молдовы. Позже, надеясь, что Польша поможет ему в освобождении Килии и Четатя Албэ, Штефан III представит (1485 г.) в Коломые вассальную грамоту королю Казимиру IV Ягелло. В приложении к этому документу секретарь польского короля написал: «Нес inscripsio ex valachico... in latinum versa est, sed rex ruthenice lingua scriptum accepif». Однако Польша не соблюдала обязанности, предусмотренные молдавско-польскими договорами. Двуличие польских, продемонстрированное еще в 1412 г. (в Договоре в Лублау), проявилось и при заключении (21.03.1489 г.) Польско-турецкого договора на 2 года. Его подписанием польское королевство соглашалось с захватом Турцией молдавских портов Килия и Четатя Албэ. Таким образом польский король Казимир IV нарушал обязательства по отношению к Молдове, взятые ранее. В ту пору престиж Молдавского государства, авторитет молдавского государя были столь известны в Европе, что Штефан III Великий не мог оставить безнаказанным подобное лицемерие, проявленное лично к нему и к его народу. Летом 1490 г. Штефан III Великий вторгается в Покутию, захватывает область и оставляет молдавские гарнизоны в крепостях. Однако Польша не отказалась от намерений подчинить себе Страну Молдавскую.

Польская кампания против Молдовы. Битва у Кодрул Козминулуй (август-октябрь 1497 г.). Польский король во главе почти 100 000-ой армии переходит Днестр у Михэлчень (август 1497 г.) и продвигается до Коцмань. Послы Молдовы, пришедшие, чтобы узнать причины этого вторжения, были взяты в плен и заточены во Львове. Подобные недипломатичные, враждебные действия выявили истинные намерения нападения Польши на Молдову. Интервенты преследовали цель захватить Молдавскую Страну и заменить Штефана III Сигизмундом, братом польского короля. Штефан III «поручил собрать все свое войско у торга Романа».

Господарь покидает Сучаву, направляясь к Роману, где собралось около 40 000 воинов-молдаван. Ожидалась и помощь со стороны Владислава II, вступившего на трон Венгрии в 1490 году после смерти Матея Корвина (Хуньяди). 26 августа поляки начинают осаду Сучавы, которая длилась «три недели, день и ночь», без каких-либо результатов. Венгерский корпус (12 000 воинов) вступает в Молдову. Его командующий начинает переговоры с воюющими сторонами. Штефан III Великий соглашается прекратить военные действия, «если поляки вернутся той дорогой, по которой вторглись». Поляки отходят из Молдовы, но не соблюдают условия Штефана, выбирая дорогу через город Сирет к Кодрул Козминулуй (возле Черновиц). 26.10.1497 г. произошла битва у Кодрул Козминулуй. Молдавское войско во главе со Штефаном III Великим атаковало польские армии. «И была тогда большая резня между молдавскими и ляхскими армиями. И были взяты все королевские скипрты, много войска и тяжелые пушки, из которых стреляли в крепость Сучаву, и были взяты тогда и многие другие, поменьше, которых невозможно перечислять». Остатки польской армии с трудом смогли дойти до Чернэуць.

29.10.1497 при битве у Ленцешть молдавское войско во главе с ворником Болдуром разбивает отряд мазурских кавалеристов, идущий на помощь полякам.

В битве у Чернэуць Штефан III Великий рассеивает остатки польской армии, изгоняя их из Молдовы. Это был последний аккорд полной победы Штефана III Великого над польскими захватчиками. Гр. Уреке пишет о «ссоре сильных мира сего»: «Бог справедливый, который осуждает несправедливость и возвышает справедливость, с особой суровостью наказывает тех, что нарушают клятву. Потому что Ольбрихт (Альберт) не неверным (туркам), а христианам хотел войну делать, не помогал тому, который покоя не имел от турков, а хотел ослабить того, который боролся с врагами христиан, именно ему должны все помогать».

Стремясь наказать польского короля за вторжение в Молдову, Штефан III Великий организует крупную кампанию против Польши (июнь 1498 г.), завоевывает и поджигает крепости Трембовля, Бучач и Подгаец, а потом направляется на Львов и за Днестр, в Покутию.

Так Штефан III Великий показал и в связи с этим конфликтом, что в последней четверти XV в. Молдова, ее господарь были силой и личностью, с которыми необходимо считаться, позицией которых в балансе европейских интересов нельзя было пренебречь. Существовало государство Молдова и ее господарь Штефан III Великий, с которыми, независимо от амбиций и претензий других, надо было договариваться и вести диалог на равных. Убедившись в этой реальности, польское королевство, при посредничестве короля Венгрии Владислава II, заключает 16.04.1499 г. Молдавско-польский договор, подтверждающий полное равенство сторон и предусматривающий оказание помощи друг другу в случае опасности. В своей окончательной форме договор был подписан в Хырлэу 10.07.1499 г. Оставался открытым вопрос о Покутии. Затягивание его решения поляками, т. е. невозвращение Польшей 3 000 рублей серебром, взятых ею в долг в 1388 г. у Петру I Мушата взамен Покутии, побудило Штефана три года спустя (октябрь 1502 г.) силой присоединить эту область к Молдове, оставить пыркэлабов и гарнизоны в крепостях, а таможенников – в городах и торгах. Штефан III Великий заявил (ноябрь 1503 г.) польскому послу Фирлею буквально: «Взял есми ту букату земле, хочу щоби мы ся ней достало». Комментируя это заявление, историк И. Богдан констатировал: «Это цитата ad literam слов Штефана – свидетельство, что он знал русский язык».