Mimo iż posiadał talent dowódczy i miał na koncie militarne sukcesy, Teodor II Laskarys w 1256 polecił go aresztować. Wówczas Michał zbiegł do TurkówT. Wolińska, Michał VIII, [w:] Paleologowie, seria: "Dynastie świata", Warszawa 2011, s. 22..
Walka o tron Paleolog schronił się wtedy w Sułtanacie Ikonium, gdzie na dworze w Ikonium zdobył zaufanie władcy. Za jego pośrednictwem miał zamiar wrócić do Nicei i walczyć o tron cesarski, jednak najazd Mongołów popsuł mu szyki. Michał walczył z Mongołami na czele oddziału złożonego z chrześcijańskich jeńców wojennych. Z czasem Teodor II wezwał Michała z powrotem do Nicei, ale potem znowu kazał go aresztować. Jakiś czas potem Michał został zwolniony z więzienia.
Okazja przejęcia władzy nadarzyła się dopiero po śmierci cesarza Teodora, którego syn, Jan IV, miał 7 lat i nie był w stanie objąć rządów w państwie. Michał z pomocą popleczników zawiązał spisek, w wyniku którego zamordowano Jerzego Muzalona – regenta wyznaczonego przez Teodora. Wtedy Michał zajął jego miejsce;