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