After John III's death in 1254, Michael briefly took service with the Seljuk Sultanate of Rum, frequent enemies of the empire, and from 1256 to 1258 he was the commander of the Christian mercenaries fighting for the Seljuk Sultan Kaykaus II. John III's son and successor, Theodore II Laskaris, recalled Michael in 1258 and after they had exchanged guarantees of safety and oaths of loyalty, Michael returned to service within the empire. Theodore II died in that same year and was succeeded by his eight-year-old son John IV Laskaris. Just a few days after Theodore's death, Michael led a coup against the bureaucrat George Mouzalon, who had been appointed regent by Theodore II. Michael seized the guardianship of the child emperor and was invested with the titles of "megas doux" and "despotes". On 1 January 1259, Michael was proclaimed as co-emperor at Nymphaion, probably without John IV being present.