The conflict between Stephen and Ottoman Sultan Mehmed II worsened when both laid their claims to the historical region of Bessarabia, now known under the name of Budjak. The region had belonged to Wallachia, but later succumbed to Moldavian influence under Petru I of Moldavia and was possibly annexed to Moldavia in the late 14th century by Roman I of Moldavia. Under Alexandru cel Bun, it had become an integral part of Moldavia and was successfully defended in 1420 against the first Ottoman attempt to capture castle Chilia. The ports of Chilia and Akkerman (Romanian: Cetatea Albă) were essential for Moldavian commerce. The old trade route from Caffa, Akkerman, and Chilia passed through Suceava in Moldavia and Lwow in Poland (now in Ukraine).
Both Poland and Hungary had previously made attempts to control the region, but had failed; and for the Ottomans, "the control of these two ports and of Caffa was as much an economic as a political necessity," as it would also give them a better grip on Moldavia and serve as a valuable strategic point from which naval attacks could be launched against the Commonwealth of Poland-Lithuania. This is confirmed by a German chronicle which explains that Mehmet wanted to turn Moldavia into "some kind of fortress," and from there, to launch attacks against Poland and Hungary. The Ottomans also feared the strategic position of Moldavia, whence it would only take 15 to 20 days to reach Constantinople.
In 1448, Petru II of Moldavia awarded Chilia to John Hunyadi, the governor of Transylvania; and in effect, it gave Hungary control of the strategic area on the Danube, with access to the Black Sea. With the assassination of Bogdan II of Moldavia in 1451 by his brother Petru Aron, the country fell into civil war, as two pretenders fought for the throne: Aron and Alexăndrel. Bogdan's son, Stephen, fled Moldavia together with his cousin, Vlad Dracula — who had sought protection at the Moldavian court – to Transylvania, at the court of Hunyadi. Even though Hungary had made peace with the Turks in 1451, Hunyadi wanted to transform Wallachia and Moldavia into a barrier that would protect the kingdom from Ottoman expansion. In the fall of 1453, after the Ottoman capture of Constantinople, Moldavia received an ultimatum to start paying tribute to the Porte; two years later, on 5 October 1455, Aron sent the first Moldavian tribute to the Porte: a payment of 2,000 ducats. With both Wallachia and Moldavia conducting a pro-Ottoman policy, the plan to install Vlad Țepeș as prince of Wallachia began to take shape. Sometime between April to July 1456, with the support of a few Hungarian troops and Wallachian boyars, Prince Vladislav II was dethroned and slain, as Vlad Țepeș took possession of the Wallachian throne; and as such, Chilia became a shared Wallachian-Hungarian possession. In April 1457, Vlad Țepeș supported Stephen with 6,000 horsemen, which the latter used to invade Moldavia and occupy the Moldavian throne, ending the civil war as Aron fled to Poland. The new prince continued sending the tribute that his uncle and Mehmed had agreed upon, and in such way, avoided any premature confrontation with his enemy. His first priority was to strengthen the country and to retrieve its lost territory. Because Aron resided in Poland, Stephen made a few incursions in southern Poland. The hostilities ended on 4 April 1459, when in a new treaty between the two countries, Moldavia accepted vassalage and Poland returned Hotin back to Moldavia; the latter also assumed the obligation to support Moldavia in retrieving Chilia and Cetatea Albă. It was also in the interest of Poland to have the area belonging to Moldavia, as it would increase their commerce in the region. On 2 March 1462, in a renewed treaty between the two countries, it was agreed that no Moldavian territory should remain under foreign rulership, and if such territory was under foreign rulership, that territory should be regained. Later that year, it is believed that Stephen asked Vlad to return Chilia back to Moldavia – a demand which was most likely refused.
On 22 June, when Vlad was fighting Mehmed, Stephen allied himself with the Sultan and with some Turkish assistance, he launched an attack on Chilia. The fortress, defended by tall stone walls and 12 cannons, was in the middle of the 15th century the strongest fortification located in the Danube area. The Wallachians rushed to the scene with 7,000 men, and together with the Hungarian garrison battled the Moldavians and the Turks for eight days. They managed to defend the town, while wounding Stephen in his foot with a shrapnel. In 1465, while Vlad was imprisoned in Hungary, Stephen again advanced towards Chilia with a large force and siege weapons; but instead of besieging the fortress, he showed the garrison – who favoured the Polish King – a letter in which the King required them to surrender the fortress. This they did, and Stephen entered the fortress where he found "its two captains, rather tipsy, for they have been to a wedding." Mehmed was furious about the news and claimed Chilia for being a part of Wallachia – which now was a vassal to the Porte – and demanded Stephen to give it over to him. The latter refused, however, and recruited an army, forcing Mehmed – who was not yet ready to wage war – to accept the situation, if only for the time being. The Moldavian prince, realising that a future war with Mehmed could not be avoided, tried to gain time by increasing his tribute to the Porte by 50 percent (to 3,000 ducats); and also sent an envoy to Constantinople with gifts for the sultan. In 1467, Matthias Corvinus of Hungary launched an expedition against Moldavia in order to punish Stephen for annexing the region. The invasion ended in a disaster for the Hungarians as they suffered a bitter defeat at the Battle of Baia, where Corvinus was thrice wounded by arrows and had to be “carried from the battlefield on a stretcher, to avoid him falling into the hands of the enemy.”
To secure his southern frontier from Ottoman threats, Stephen wanted to liberate Wallachia – where the hostile Radu the Handsome, the halfbrother of Vlad Țepeș ruled – from Ottoman dominion. In 1470, he invaded the country and burned down the town of Brăila and in 1471, Stephen and Radu confronted each other in Moldavia, where the latter was defeated. Meanwhile, Genoa, which possessed several colonies in the Crimea, began to worry about Stephen's growing influence in the region; and ordered her colonies to do whatever was needed to revenge past mischief from which allegedly, the Genovese had suffered. The colonies in turn pursued the Tatars to attack Moldavia. Later that year, the Tatars invaded the country from the north, causing great damage to the land and enslaving many. Stephen replied by invading Tatar territory with Polish assistance. In 1472, Uzun Hassan of Ak Koyunlu invaded the Ottoman Empire from the east, causing a great crisis to the empire. He was defeated the following year, but this unexpected event, as it is explained in a contemporary source, encouraged Venice and Hungary to renew their war on the Ottomans, and Moldavia to free herself from any Ottoman influence. In 1473, Stephen stopped paying the annual tribute to the Porte and as a reaction to this, an Italian letter, dated from 1473 to Bartolomeo Scala, secretary of the Republic of Florence, reveals that Mehmed had left Constantinople on 13 April and was planning to invade Moldavia from land and sea. Stephen still hoped to make peace with Radu and asked the Polish king to work as mediator. The peace attempts failed and the conflict intensified with three leaders challenging each other for the Wallachian throne: Radu, who was supported by Mehmed; the seemingly loyal Basarab Laiotă, who at first was supported by Stephen; and Basarab Ţepeluş cel Tânăr—who would gain the support of Stephen after Laiotă's betrayal. A series of "absurd" clashes followed, starting with another confrontation between Stephen and Radu on 18–20 November, at Râmnicu Sărat, where the latter suffered his second defeat at the hands of the Moldavian "warlike" prince. A few days later, on 28 November, the Ottomans intervened with an army consisting of 12,000 Ottomans and 6,000 Wallachians, but "they incurred heavy losses and fled across the Danube." After capturing the castle of Bucharest, Stephen put Laiotă on the throne, but on 31 December, a new Ottoman army of 17,000 set camp around river Bârlad, laying waste to the countryside, and intimidating the new prince into abandoning his Wallachian throne and fleeing to Moldavia. In the spring of 1474, Laiotă took the Wallachian throne for the second time; and in June, he made the decision to betray his protégé by submitting to Mehmet. Stephen then invested his support into a new candidate, named Ţepeluş (little spear), but his reign was even shorter, as it only lasted a few weeks after being defeated by Laiotă in battle on 5 October. Two weeks later, Stephen returned to Wallachia and forced Laiotă to flee. Mehmed, tired of what transpired in Wallachia, gave Stephen an ultimatum to forfeit Chilia to the Porte, to abolish his aggressive policy in Wallachia, and to come to Constantinople with his delayed homage. The Prince refused and in November 1474, he wrote to the Pope to warn him of further Ottoman expansion, and to ask him for support.