Тридцатичетырехлетний Михаил во многих отношениях был очевидной кандидатурой: он мог претендовать на родство с семействами Дука, Ангел и Комнин, а его жена Феодора была внучатой племянницей Иоанна Ватаца. Его соучастие в убийстве Музалона следовало бы считать пятном на его репутации, но протовестиария так сильно ненавидели, что на это не обратили внимания. Михаил Палеолог пользовался огромной популярностью в армии, а священники были о нем хорошего мнения. Ему был дарован титул великого дуки (мегадукса)[87], а вскоре и титул деспота; наконец, в ноябре 1258 года его подняли на щит и провозгласили соправителем, а на Рождество короновали в Никее. Вначале императорские короны, богато украшенные драгоценными камнями, возложили на головы Михаила и Феодоры и лишь потом тонкую нить жемчуга надели на голову юного императора Иоанна IV.

Мало кто из собравшихся сомневался, что именно Михаил VIII Палеолог поведет своих подданных в столицу, однако прежде ему требовалось встретиться еще с одним врагом. В начале 1256 года король Сицилии Манфред, незаконнорожденный сын Фридриха II, вторгся в Эпир и захватил Корфу. Ранее деспот Михаил объединился с ним против Никеи, пообещав руку своей старшей дочери Елены. Манфред согласился и отправил новоиспеченному тестю 400 конных рыцарей из Германии. Вскоре к этому союзу присоединился и правитель Ахейского княжества Гильом II Виллардуэн, женившийся на второй дочери Михаила Анне. Конечной целью операции был Константинополь, что, безусловно, означало, что по дороге придется захватить Фессалоники.

Таким образом, когда воцарился Михаил Палеолог, против него выступила практически вся материковая Греция. К счастью, он отправил на Балканы большой экспедиционный корпус под командованием своего брата, севастократора Иоанна Палеолога, и великого доместика Алексея Стратигопула и в начале 1259 года приказал им выступить против врага. Две армии сошлись у Пелагонии, и коалиция практически сразу распалась. Деспот Михаил и его сын Никифор, ошибочно заподозрив союзников в предательстве, покинули лагерь и сбежали. Еще один сын, Иоанн I Комнин Дука, над которым Виллардуэн насмехался из-за его незаконнорожденности, со злости присоединился к никейцам. К началу битвы Иоанн Палеолог обнаружил, что против него выступила лишь кавалерия Виллардуэна и Манфреда, которые оказались беззащитны перед его половецкими лучниками. Рыцари Манфреда сдались и были взяты в плен, как и сам Виллардуэн, которого позже нашли прячущимся в стоге сена недалеко от Кастории и узнали только по торчащим вперед зубам. После этого Иоанн пошел дальше через Фессалию, а Алексей направился в Эпир и захватил его столицу Арту. Победа была полной.