After the Moldavian loss of Chilia and Cetatea Albă, the Ottoman threat seemed more evident. John I Albert was suzerain of Moldavia, and, when Ștefan asked him for military assistance, they met in 1494 at the conference of Levoča, where together with King Ladislaus II of Hungary and Elector Johann Cicero of Brandenburg, they forged plans for an expedition against the Porte. The objective was to recapture Chilia and Cetatea Albă. It took Poland three years to complete preparations. Their army was made of Polish Crown forces, aided by a number of foreign mercenaries, 400 Teutonic Knights under Grand Master Johann von Tieffen, and a 600 strong unit from Mazovia. Altogether, the Polish army was some 40,000 strong, with 200 cannons.

However, in unexplained circumstances, Ștefan received reports from Hungary that John I Albert prepared to place his own brother, the Polish prince Sigismund (later king, as Sigismund I the Old), on the Moldavian throne.

The campaign started on the wrong foot, with John I Albert entering Moldavia at Hotin and - despite sound advice to the contrary - deciding not to take the fortress, but to go straight for the capital city of Suceava. Later, this would prove a fatal mistake: by this time Stephen's scorched earth tactics were already common knowledge, as he had used it successfully several times before against the Hungarians and the Ottomans; yet John I Albert failed to secure his communication lines with Poland. Supply from home proved impossible and the Poles were forced to live off an already depleted land.