Diplomacy and conquest
In the words of Geanaklopos, "With the fall of Constantinople, the papacy suffered not only a loss of political prestige but severe damage to its spiritual authority as well. For the Greeks had now effectively reasserted their right to a church divorced from Rome. Thus it became the task of each of the six successive popes of Michael's reign to accomplish the return of the schismatics to the Roman fold." Michael was aware of the immense influence the Curia had in the West, so he immediately dispatched an embassy to Pope Urban IV consisting of two envoys; upon reaching Italy, the men were seized and one was flayed alive, while the other succeeded in escaping back to friendlier territories.
Michael also approached Manfred of Sicily to achieve some kind of accord. In the summer of 1262, Michael offered to divorce his wife Theodora and marry Manfred's sister Anna. This offer failed spectacularly: not only did Anna reject his proposal, Theodora turned to Patriarch Arsenios for help. The Patriarch confronted the emperor and pressured him to abandon his plans. Michael yielded and sent Anna back to her brother with gifts. This gesture helped to secure the release of his general Alexios Strategopoulos.
It was around this time that Michael was presented with a dangerous distraction: ʿIzz ad-Dīn Kaykāwūs, who had been deposed as Sultan of the Seljuk Turks by a coalition led by the Pervane Mu‘in al-Din Suleyman, arrived seeking help from his old friend. But as Claude Cahen notes, he "was to be cruelly disappointed." Michael favored the Mongols of Iran, who supported ʿIzz ad-Dīn's enemy the Pervane, against those of Russia. Further, he could not risk a war on his Asian frontier while Western Europe, infinitely more dangerous, was opposed to him. Cahen believes that either ʿIzz ad-Dīn became an embarrassment, or perhaps the former Sultan "indulged in too open of criticism"; in either case, ʿIzz ad-Dīn was imprisoned. Mongol troops from Russia eventually freed him, and carried him off to the Crimea where he lived out his life.
A series of military setbacks followed. In 1263 Michael sent 15,000 men, including 5,000 Seljuk mercenaries, to Morea with the goal of conquering the Principality of Achaea, but this expedition failed in a surprise rout at Prinitza. Later that year a mixed fleet of 48 imperial and Genoese ships was defeated by a smaller Venetian force at the Battle of Settepozzi. The following year, the imperial forces in Morea were again defeated at Makryplagi after the Seljuk mercenaries, who had not been paid, changed sides. The nadir of Michael's disasters came in the Spring of 1265, when an army of Tatars and Bulgars under Nogai Khan ravaging Thrace ambushed Michael Palaeologos when he was returning to Constantinople accompanied by only a few troops. Deserted by even his own officers, who fled to save their own lives, Michael was able to escape by crossing the Ganos Mountains and reaching the Marmora coast, where he happened upon two Latin ships. He quickly boarded the vessels, and two days later safely arrived at Constantinople. "Thus did Michael survive one of the narrowest escapes of his career," notes Geanakoplos.
The military advantages Michael enjoyed after capturing Constantinople had evaporated, but he would demonstrate his diplomatic skills to successfully recover from these drawbacks. After Settepozzi, Michael VIII dismissed the 60 Genoese galleys that he had hired earlier and began a rapprochement with Venice. Michael secretly negotiated a treaty with the Venetians to grant terms similar to those in the case of Nymphaeum, but Doge Raniero Zeno failed to ratify the agreement. He also signed a treaty in 1263 with the Egyptian Mamluk sultan Baibars and Berke, the Mongol Khan of Kipchak Khanate.