Несмотря на реабилитацию, подозрения в отношении Палеолога не рассеялись даже после смерти Иоанна III и воцарения Феодора II. Учитывая последующие события, они могли быть вполне оправданны. Палеолог жил под постоянным страхом ареста и опасался, что его могут ослепить просто в качестве меры предосторожности. Феодор II уже показал, что может быть, когда нужно, совершенно безжалостным. Он устроил брак своей дочери и сына правителя Эпира, но, когда молодой человек и его мать прибыли в Фессалоники на церемонию, заточил их и отказывался освободить, пока ему не отдали порт Диррахий. Палеолог решил не рисковать. Осенью 1256 года, пока император был на Балканах, он бежал за границу ко двору сельджукского султана в Конью (Иконион). Но в следующем году согласился вернуться после того, как Феодор II поклялся не преследовать его, а Палеолог, в свою очередь, пообещал никогда не пытаться захватить трон.
Однако в августе 1258 года Феодор II заболел и скончался. Перед смертью он успел назначить регентом малолетнего Иоанна IV своего главного министра Георгия Музалона. Этот выбор не понравился многочисленным врагам Феодора II, которых тот успел нажить за свое короткое правление, и Музалон оставался регентом недолго. Через три дня после погребения императора в монастыре, где он был похоронен, состоялась поминальная служба. На улице собралась большая и грозная толпа знатных людей из тех, кто затаил злобу на покойного императора. По данному им знаку они обнажили мечи и ворвались в церковь. Хор замолк, священник, который проводил службу, благоразумно скрылся. Регент Музалон и его братья, понимая, что пришли за ними, попытались спрятаться. Но зоркий латинский наемник заметил колени Музалона, торчавшие из-под алтаря. Регента вытащили из его убежища и буквально изрубили на куски.
Михаила Палеолога среди злодеев вроде бы не было, однако трудно поверить, что он не был причастен к произошедшему, учитывая, что именно Палеолог больше других выиграл от этого убийства. Он и его братья сразу же взяли юного императора под свою защиту, и через несколько недель Михаил был признан регентом и опекуном Иоанна. Еще через несколько месяцев он почувствовал себя достаточно уверенно для того, чтобы сделать следующий шаг и короноваться как император Михаил VIII (правил в 1259–1282 гг.), последовав традиционной схеме и разделив престол с законным наследником Иоанном IV. Потеснив таким образом династию Ласкарисов, Михаил продолжил действовать с того места, где остановился Иоанн III, и риторика возрождения империи и священной задачи возвращения Константинополя зазвучала как никогда громко. Михаил не упускал возможности представить себя законным наследником византийских императоров прошлого. Подходящий случай подвернулся, в частности, когда он вел военную кампанию во Фракии в 1260 году. Кто-то из его офицеров сообщил ему, что их разъезд оказался в пределах видимости стен Константинополя. Укрепления надежно защищались латинянами, и никакой надежды попасть внутрь не было, поэтому разъезд поскакал в сторону пригорода Хебдомон. Там солдаты наткнулись на заброшенный монастырь, который использовался как хлев. Войдя в полуразрушенную церковь, они с удивлением увидели в углу человеческий скелет – без рук и без ног, а какой-то шутник вставил ему в рот пастушью дудочку. Рядом стоял пустой саркофаг, и один солдат нагнулся, чтобы прочитать надпись: «Всю жизнь неусыпно оберегал детей Нового Рима». Тогда солдаты поняли, что перед ними останки самого Василия II Болгаробойцы. Когда Михаил услышал это, он приказал облачить скелет в шелковые одежды и поместить его в богато украшенный гроб. Затем его перевезли в соседнюю Силимврию и там перезахоронили со всеми почестями, какие только мог один византийский император оказать другому.