Cu toate că Moldova prin actele semnate anterior era, adică, sub oblăduirea suzerană a Poloniei, Ştefan în 1457 şi 1458 întreprinde expediţii în regiunile sudice ale Poloniei, intenţionînd să-l prindă pe Petru Aron, ucigaşul tatălui său. Implicată în conflicte cu teutonii, Polonia n-a replicat. Din contra. A acceptat şi a semnat Tratatul moldo-polon de la Overhelăuţi (1459), prin care Ştefan a obţinut ce a dorit. Mai mult, în urma unei înţelegeri din 1462, un an mai tîrziu (1463), Hotinul, cedat Poloniei de Petru Aron, reintră în stăpînirea Moldovei. Satisfăcînd pretenţiile mai mult ceremoniale ale suveranilor poloni, Ştefan semnează la 28.07.1468 un nou Tratat moldo-polon, prin care domnul Moldovei confirmă relaţiile bilaterale stabilite anterior. Regele polon se obligă să nu adăpostească nici un pretendent la tronul Moldovei. Ulterior, nădăjduind că Polonia îi va da ajutor pentru reîntoarcerea Chiliei şi a Cetăţii Albe, Ştefan al III-lea, însoţit de mari boieri, prestează (1485) la Colomeea omagiu regelui polon Cazimir al IV-lea Iagello. (În plus la jurămîntul depus de domnul Moldovei secretarul regelui polon nota: „hec inscripsio ex valachico... in latinum versa est, sed rex ruthenice lingua scriptum accepit”. Polonia însă nu-şi respecta obligaţiile prevăzute în acordurile moldo-polone. Atitudinea duplicitară a Poloniei, demonstrată încă în 1412 în Tratatul de la Lublau, s-a manifestat şi prin încheierea la 21.03.1489 a acordului polono-turc pe doi ani. Prin semnarea lui, regatul polon recunoştea stăpînirea otomană asupra cetăţilor-porturi moldoveneşti Chilia şi Cetatea Albă. Astfel regele polon Cazimir al IV-lea încălca angajamentele luate la Colomeea faţă de Moldova. În acea perioadă prestigiul Statului Moldovenesc, autoritatea suveranului său erau atît de bine cunoscute în Europa, încît Ştefan cel Mare nu putea lăsa nepedepsită atare făţărnicie, arătată ţării şi poporului său. În vara anului 1490 Ştefan cel Mare pătrunde în Pocuţia, pune stăpînire pe ţinut, pune garnizoane moldoveneşti în cetăţi. Polonia însă nu a renunţat la intenţia de a supune Ţara Moldovei.

Campania polonă împotriva Moldovei (august-octombrie 1497). Bătălia de la Codrul Cosminului. Regele polon Ioan Albert, în fruntea unei armate de aproape 100.000 de oşteni, trece Nistrul pe la Mihălceni (9 august) şi înaintează pînă la Coţmani. Solii Moldovei, timişi în întimpinare pentru limpezirea situaţiei şi aflarea motivelor acestei năpădiri, au fost luaţi prizonieri şi închişi în cetatea Lvovului. Aceste acţiuni nediplomatice, duşmănoase au scos la iveală intenţiile adevărate ale năvălirii polonilor în Moldova. Invadatorii urmăreau ţelul să supună Ţara Moldovei şi să-l înlocuiască pe domnul ei cu Sigismund, fratele craiului polon. Ştefan cel Mare „a poruncit să se adune toată oastea sa la tîrgul Romanului”. Domnul Moldovei părăseşte Suceava, îndreptîndu-se spre Roman, unde se strînse armata – aproape 40 000 mii de oşteni moldoveni. Se aştepta un ajutor armat din partea regelui Ungariei Vladislav al II-lea. La 26 august polonii încep asediul Sucevei, care a ţinut „trei săptămîni zi şi noapte”, fără vreun oarecare rezultat. Corpul de oaste ungur (12.000 de oşteni) pătrunde în Moldova. Conducătorul ungur începe tratativele cu părtaşii în conflict. Ştefan cel Mare acceptă să se termine atacurile, „dar în aşa chip ca ei (polonii) să se întoarcă pe aceeaşi cale pe unde au venit”. Polonii se retrag din Moldova, dar nu respectă condiţia pusă de Ştefan cel Mare, alegînd drumul prin oraşul Siret spre Codrii Cozminului, lîngă Cernăuţi. La 26 octombrie are loc Bătălia din Codrul Cozminului. Oastea moldovenească în frunte cu Ştefan cel Mare, atacă armata polonă: „Şi a fost atunci măcel mare între armatele moldoveneşti şi leşi. Şi au fost luate toate schiptrele crăieşti şi au căzut acolo multă oaste şi toate tunurile cele mari, cu care bătuse în cetatea Sucevii, au fost luate atunci şi altele şi mai mici multe, pe care nu este cu putinţă a le înşira”. Rămăşiţile armatei polone au putut ajunge cu greu pînă la Cernăuţi.

Lupta de la Lenţeşti. La 29 octombrie oastea moldovenească în frunte cu vornicul Boldur, înfrînge un detaşament de cavaleri mazuri care venea în ajutorul oştilor polone.

Lupta de la Cernăuţi. La 30 octombrie Ştefan cel Mare împrăştie resturile armatei polone, alungîndu-le din ţară. Acesta a fost ultimul acord al biruinţei depline a lui Ştefan cel Mare asupra năvălitorilor poloni.

Scrie Gr. Ureche despre „certarea celor puternici”: „Dumnezeu cel dreptu, cela ce ceartă nedreptatea şi înalţă dreptatea, cu cîtă certare pedepseşte pe ceea ce calcă jurămîntul. Că acest Olbrihtu nu spre păgîni, ci spre creştini vrea să facă războiul, nu da ajutor aceluia ce nu avea odihnă de turci, ci vrea să slăbească pe cela ce lupta cu vrăjmaşii creştinilor, pe carele trebuia cu toţii să-l ajutorească”. Vrînd să pedepsească regele polon pentru atacul din anul precedent asupra Moldovei, Ştefan al III-lea cel Mare organizează o campanie masivă în Polonia (iunie 1498); cucereşte şi arde cetăţile Trembowla, Buciaci şi Podhaeţ, apoi pînă la Lvov şi peste Nistru, în Pocuţia. Astfel Ştefan al III-lea cel Mare a demonstrat şi cu prilejul acestui conflict, că în ultimul pătrar al veacului al XV-lea Moldova, întîi de toate – domul ei erau o forţă şi personalitate, de care trebuia să se ţină cont numaidecît, poziţia cărora în balanţa intereselor europene nu putea fi deloc neglijată. Există un stat – Moldova, cu un domnitor – Ştefan al III-lea cel Mare cu care, indiferent de ambiţiile şi pretenţiile altora, trebuia să se negocieze şi să se dialogheze de la egal la egal. Convins, după toate, de această realitate, regatul polon, prin mijlocirea regelui Ungariei Vladislav al II-lea, încheie (16.04.1499) Tratatul de pace moldo-polon, ce confirma egalitatea deplină a ambelor state, prevăzîndu-se că ele îşi vor acorda ajutor în caz de primejdie. În forma sa definitivă tratatul s-a semnat la Hîrlău la 10.07.1499. Rămînea deschisă problema Pocuţiei.

Tărăgănarea de către poloni a lichidării „chestiunii Pocuţiei” (achitarea de către Polonia a celor 3000 ruble de argint împtumutate în 1388 de la Petru I Muşat în schimbul Pocuţiei) l-a făcut pe Ştefan ca trei ani mai tîrziu (octombrie 1502) să ocupe această regiune, să instaleze pîrcălabi şi garnizoane în cetăţi, vameşi în oraşe şi tîrguri.

Avînd în vedere Pocuţia, Ştefan al III-lea cel Mare declară (noiembrie 1503) solului polon Firley: „взял есми ту букату земле, хочу щоби ми ся ней достало”. În limba moldovenească această frază rusească înseamnă: „am luat această bucată de pămînt, vreau să-mi rămînă mie”. Pe marginea ei Ioan Bogdan conchide: „Acestă citaţie ad literam a cuvintelor lui Ştefan e o dovadă că el ştia ruseşte”.