Z tego powodu, gdy w czerwcu 1497 Jan I Olbracht ruszył na Mołdawię, by odbić Kilię i Białogród, Stefan zerwał związek lenny z Polską uznając się za lennika tureckiego. Otrzymał on posiłki tureckie, a także węgierskie. Wojska Olbrachta bez powodzenia oblegały od 24 września do 18 października Suczawę – wobec odcięcia ich przez Stefana od zaopatrzenia i widma głodu, zawarty został rozejm i Polacy rozpoczęli odwrót. Wskutek jednak powstałego nieporozumienia Stefan uderzył na wycofujących się przez Bukowinę ku Śniatyniowi Polaków i rozbił ich 26 października pod Koźminem. W 1498 to hospodar mołdawski uderzył na Polskę, pustosząc ziemie przygraniczne. Pokój został podpisany w 1499, dzięki niemu został m.in. stracony w Czchowie w 1501 przebywający w Polsce Eliasz, syn Piotra Arona, jeden z przywódców opozycji przeciwko Stefanowi.
W 1502 na wieść o śmierci Jana Olbrachta zajął Pokucie, uprzednio sprzymierzony z Turcją i Moskwą.