Феодор II успел назначить опекунами своего восьмилетнего сына Иоанна IV Дуки Ласкаря Константинопольского патриарха Арсения Авториана (1255–1260, 1261–1265 гг.) и протовестария Георгия Музалона, который первоначально намеревался отказаться от этого назначения, однако был поддержан Михаилом Палеологом и согласился стать опекуном. 24 августа 1258 г., во время панихиды по императору Феодору II, совершавшейся на его могиле в Сосандрском монастыре, заговорщики, к которым примкнул Михаил Палеолог, убили Георгия Музалона и двух его братьев. Регентство перешло к Михаилу Палеологу как к лицу, исполнявшему обязанности великого коноставла. В сентябре 1258 г. он удостоился титула великого дуки, а 13 ноября был провозглашён деспотом и василеопатром. Получив доступ к государственной казне, Михаил Палеолог щедро раздавал деньги чиновникам, военным, духовенству, пытаясь заручиться их поддержкой. На важные должности он назначил своих сторонников и родственников (так, его брат стал великим доместиком), противники же Михаила Палеолога были удалены из столицы. Вскоре Михаил Палеолог был провозглашён императором Никейской империи. Арсений Авториан, первоначально не желавший признавать его правителем из-за опасений за жизнь Иоанна IV Дуки Ласкаря, всё же согласился совершить коронацию Михаила Палеолога (1 января 1259 г.) при условии, что тот будет лишь соправителем Иоанна IV Дуки Ласкаря вплоть до его совершеннолетия. Однако, видя стремление Михаила Палеолога отстранить Иоанна IV Дуку Ласкаря от власти, Арсений Авториан временно удалился с патриаршего престола. Новым патриархом стал Никифор II, который вскоре скончался, после чего Михаил Палеолог примирился с Арсением Авторианом и вернул его на престол. Усилению позиций Михаила Палеолога способствовали его успехи на внешнеполитической арене. Главная опасность для балканских владений Никейской империи исходила от деспота Эпира Михаила II Комнина Дуки (около 1230 – 1266/1268 гг.), заключившего союз с королём Сицилии Манфредом (1258–1266 гг.) и правителем Ахейского (Морейского) княжества Гийомом II Виллардуэном (1246–1278 гг.). После ряда успешных сражений Михаила Палеолога против этой коалиции состоялась решающая битва при Пелагонии в Западной Македонии (сентябрь 1259 г.). Войско под командованием брата Михаила Палеолога севастократора Иоанна Палеолога, состоявшее из византийцев, сельджуков и куманов, нанесло поражение объединённым силам Морейского княжества и Эпирского деспотата. Князь Гийом II попал в плен и был вынужден в обмен на свободу уступить Никейской империи ряд крепостей на Пелопоннесе (Монемвасию, Мистру, Майну и Иеракий). Вскоре князь Гийом II стал восприемником одного из сыновей Михаила Палеолога. Победа в битве при Пелагонии имела важное значение в деле восстановления Византийской империи: Эпир, утративший ряд территорий, больше не представлял угрозы; Латинская империя, сузившаяся до территорий вокруг Константинополя, уже не рассчитывала на силы Ахейского княжества; византийцы получили опорные пункты на Пелопоннесе.