Такое постыдное обращение с одним из самых выдающихся полководцев подтвердило давно уже созревшее у никейцев убеждение в том, что император не способен более ответственно управлять страной. И, вне всякого сомнения, произошел бы государственный переворот, если бы Феодор — весьма кстати — не заболел в августе 1258 г.; к этому моменту ему исполнилось тридцать шесть лет. Поскольку его старший сын Иоанн не достиг еще совершеннолетия, он назначил регентом Георгия Музалона, к которому никейцы относились с неприкрытой ненавистью. Находясь на смертном одре, Феодор заставил членов самых видных аристократических семейств принести клятву верности и Иоанну, и Георгию, но во время поминальной службы, состоявшейся через девять дней, Музалона убили прямо у главного престола и разрубили его тело на куски. Затем последовал дворцовый переворот, результатом которого стало определение на верховную должность спешно освобожденного Михаила Палеолога, который, возможно, и явился подстрекателем заговора.
Михаил, которому к этому времени исполнилось тридцать четыре года, во многих отношениях представлял собой очевидную кандидатуру. Он состоял в родстве с домами Дуков Ангелов и Комнинов, а его жена Феодора была внучатой племянницей Иоанна Ватаца. Причастность Михаила к убийству Музалона должна была бы выглядеть пятном на его репутации, но протовестиария все настолько ненавидели, что на эту деталь в биографии нового правителя смотрели сквозь пальцы. Он продолжал пользоваться исключительной популярностью в армии, и у него была хорошая репутация в глазах духовенства. Михаилу присвоили титул великого князя (megas dux), а вскоре после этого — деспота. Наконец в ноябре 1258 г. он был поднят на щит и провозглашен соправителем императора; его коронация прошла в Никее в день Рождества. Сначала коронованы были он и его жена Феодора — императорскими диадемами, украшенными драгоценными камнями, — и только после этого тонкая нить с жемчугами была возложена на голову Иоанна IV.
В империи мало кто сомневался в том, что Михаил VIII Палеолог отвоюет наконец Константинополь. Но прежде предстояло столкнуться еще с одним врагом. В начале 1258 г. Манфред Сицилийский, внебрачный сын Фридриха II, вторгся в Эпир и занял Корфу. Деспот Михаил принял сторону Манфреда в его противостоянии с Никеей и предложил ему руку своей старшей дочери Елены. Манфред принял предложение и прислал новоиспеченному тестю 400 конных рыцарей из Германии. Вскоре после этого к новому союзу присоединился Вильгельм де Виллардуэн, латинский князь Ахеи, который взял себе в жены вторую дочь Михаила Анну. Конечной целью экспедиции был Константинополь, но попутно она, естественно, предполагала захват Фессалоник.
Так, ко времени восшествия на престол Михаила Палеолога практически вся материковая часть Греции ополчилась против него. К счастью, еще до этого Михаил направил на Балканы большой экспедиционный корпус под начальством своего брата, севастократора Иоанна Палеолога, и великого доместика Алексея Стратегопула. И в начале 1259 г. Михаил повелел им выступить против врага. Две армии сошлись при Пелагонии, и почти немедленно антиникейская коалиция распалась. Деспот Михаил и его сын Никифор, ошибочно решив, что союзники собираются предать их, оставили лагерь и бежали. Другой сын Михаила, Иоанн Бастард, над которым Виллардуэн имел обыкновение насмехаться по причине незаконнорожденности, примкнул к никейцам из-за задетого самолюбия. К началу сражения Иоанн Палеолог обнаружил, что против него выступает только кавалерия Виллардуэна и Манфреда. Но она оказалась бессильна против половецких лучников. Рыцари Манфреда сдались и были взяты в плен, как впоследствии и сам Виллардуэн, которого обнаружили спрятавшимся в стоге сена в окрестностях Кастории — его опознали по характерным выступающим вперед зубам. Затем Иоанн решил идти через Фессалию, тогда как Алексей направился прямо в Эпир и занял его столицу Арту. Победа была полной.
К этому времени всем стало ясно, что отвоевание Константинополя представляет собой лишь вопрос времени и к тому же — весьма непродолжительного. У Балдуина из всех его былых союзников остались только папство и Венеция. Александр IV, однако, не проявлял интереса к проблемам, стоявшим перед Балдуином, так что император мог рассчитывать лишь на венецианцев, которым Латинская империя была обязана в наибольшей степени своим становлением, а их флотилия в 30 судов до сих пор патрулировала Босфор. Но вскоре ценность венецианской помощи также оказалась под вопросом, поскольку 13 марта 1261 г. Михаил Палеолог, крайне нуждавшийся в кораблях, подписал с Генуей договор, по которому генуэзцы предоставляют никейцам суда, а получают все те концессии, ранее предоставляемые Венеции — в частности, им был обещан собственный квартал в Константинополе и других основных портах империи, а также свободный доступ к черноморским портам. Для Генуи это соглашение стало историческим, поскольку заложило фундамент ее будущей коммерческой империи на Востоке.