Road to the throne
Michael VIII Palaiologos was the son of the megas domestikos Andronikos Palaiologos by Theodora Angelina Palaiologina, the granddaughter of Emperor Alexios III Angelos and Euphrosyne Doukaina Kamaterina. According to Deno John Geanakoplos, Michael's ancestry could be traced back to all three imperial houses that ruled the empire in the centuries before the capture of Constantinople in 1204 by the Fourth Crusade. His mother does not appear to have played a significant role in his early life; at least for a time he was brought up by his elder sister Martha, the wife of megas domestikos Nikephoros Tarchaneiotes, although she was only ten years older than he.
Michael rose to distinction at an early age, serving as the governor of the Thracian towns of Melnik and Serres under the command of his father Andronikos. However, in the autumn of 1253 Michael was accused before the Emperor John III Vatatzes of plotting against the throne. The only way Michael was allowed to prove his innocence was through trial by ordeal, holding a red-hot iron. When the Emperor ordered him to take hold of the red-hot metal, the young Michael answered (to use Geanakoplos' words) "with the astuteness that was to characterize his later career as Emperor": if the Metropolitan Phokas of Philadelphia, who evidently supported this proposal, could take the iron from the altar with his own hands and place it in Michael's, he would gladly receive it in faith that the truth would be revealed.
Although Michael avoided punishment, and afterwards was married to the Emperor's granddaughter and appointed megas konostaulos of the Latin mercenaries in the employment of the emperors of Nicaea, he was still mistrusted. Following the death of John Vatatzes, Michael crossed the Sangarios River with a few close friends and took service with the Seljuk Sultanate of Rum. From late 1256 to 1258 he served as commander of the Christian mercenaries fighting for Sultan Kaykaus II; in that later year the Emperor Theodore II Doukas Laskaris recalled Michael, and after both exchanged oaths of loyalty and guarantees of safety, Michael returned to the service of the Emperor.
A few days after the death of Emperor Theodore Laskaris in 1258, Michael Palaiologos instigated a coup against the influential bureaucrat George Mouzalon, seizing from him the guardianship of the eight-year-old Emperor John IV Doukas Laskaris. Michael was invested with the titles of megas doux and, in November 1258, of despotēs. On 1 January 1259 Michael VIII Palaiologos was proclaimed co-emperor at Nymphaion.