Troubled as relations with the Habsburgs were, they were as nothing compared to the problems posed by the rise of the Ottoman Empire. Poland had only a limited role in Wladyslaw Ill’s disastrous Varna campaign, primarily a Hungarian undertaking. With the fall of Constantinople to Mehmet II in 1453, it was clear that the Ottoman empire had become an established, permanent fixture of the European scene. Both he and his successors were eager to extend their European possessions and to build up their hold on the Black Sea basin. In 1475, the Tatars of the Crimea acknowledged Turkish sovereignty, accepting Turkish garrisons in their coastal towns. While difficulties of supply, terrain and distance made it difficult for the Turks to annex outright the Danubian principalities of Wallachia and Moldavia - the latter a vassal state of Poland since Jagiello’s accession - it was clear that they had little hope of maintaining their independence intact.
Moldavia’s bospodars could preserve a degree of freedom of action only by manoeuvring between their more powerful neighbours of Poland, Turkey and Hungary: in practice, this meant siding with whichever of these powers appeared to be the strongest at any given moment. Casimir IV gave his tacit approval to the annual tribute of 2,000 ducats which Stephen the Great of Moldavia (reigned 1457-1504) paid to the Sultan as a token symbol of Turkish suzerainty - after all, Polish and Lithuanian rulers, too, paid such sums to the Tatars of the Volga and the Crimea in order to persuade them (with only limited success) not to raid their lands. Poland and Hungary were both rivals for influence in Moldavia - and the rivalries prevented them from co-operating. With Hungarian help, Stephen was able to thwart Turkish efforts in 1475 and 1476 to annex his Black Sea ports of Kilia and Akerman (Belgorod), but he was unable to stop them falling to a huge Turkish-Tatar army in .1484. Polish help allowed him to recover some lost ground in T485, but both ports remained in Ottoman hands. The Poles infuriated Stephen by agreeing to a truce which preserved the new status quo, and deprived him of the two ports, and which also allowed their own merchants freedom to trade in them; he had to continue to acknowledge Polish suzerainty, pay tribute to Turkey and suffer the loss of two of his most important commercial centres.
It was a deep humiliation. Stephen and his successors took their fury out by attempting to wrest from Poland the border territory of the Pokucie (Pokutija). In 1497, John Albert, in yet another of his ill-considered forays, led a major expedition into Moldavia, ostensibly to try once more to throw the Turks out of Kilia and Belgorod, but in reality to place his younger brother, Sigismund, on the principality's throne. The siege of Stephen’s capital, Suyeava, was a dismal failure and John Albert’s retreating army suffered heavy losses. Though the disaster meant the effective abandonment of Polish claims to suzerainty, Moldavian raids into Pokucie intensified and relations with Moldavia remained a thorn in Poland’s side until Suleiman the Magnificent asserted a much closer control over his (no longer Poland’s) vassal state after 1538.