Василевс вернулся в свою столицу. Городские колокола возвестили об этом торжественном событии, и во всех церквях был отслужен благодарственный молебен. Однако Михаил Палеолог не принимал участия в этих празднествах. Когда он по возвращении увидел город, зрелище глубоко поразило его. Повсюду царила разруха: церкви находились в руинах, от дворцов остались одни остовы, целые кварталы являли собой груду почерневшей древесины. Значительная часть развалин и обломков пребывала в неизменном виде на протяжении более полувека, с того времени, когда город был разрушен крестоносцами. После коронации Михаил уединился в старом дворце – Влахернский, по его мнению, был осквернен пребыванием латинян, – чтобы хорошенько обдумать проблемы, стоявшие перед ним.
Наиболее важной из них являлась проблема государственной безопасности. Большая часть Греции все еще находилась под властью франков; Эпир и Фессалия, хотя и управлялись греками, были враждебно настроены по отношению к константинопольской власти – так же как Сербия и Болгария. Венеция и Генуя контролировали византийское морское пространство и значительную часть Восточного Средиземноморья. Папа Урбан IV, бывший латинский патриарх Иерусалима, отказывался смириться с крушением крестоносной империи, а Манфред, к тому времени вернувшийся на Сицилию, был готов использовать любой предлог для нового наступления на Константинополь. Союз нескольких этих врагов – а то и всех сразу – мог уничтожить только что восстановленную, еще не окрепшую империю.
Оценив со всех сторон ситуацию и посчитав, что на Западе можно рассчитывать только на поддержку генуэзцев, василевс решил в первую очередь восстановить сухопутные и приморские стены, а также огромную железную цепь, перегораживавшую ранее Золотой Рог. Далее Михаил приступил к строительству, но не забывал и о разрушенных монастырях и церквях, сознавая их жизненную важность для укрепления народного духа. Пробуждение религиозной жизни его подданных одновременно приводило к укреплению их чувства патриотизма и национальной гордости; в то же время все это обеспечивало поддержку политики Михаила со стороны церковных кругов. Венцом усилий василевса стало возведение перед церковью Св. Апостолов колонны, которую увенчивала статуя его покровителя, св. Михаила, а у подножия колонны стояла еще одна статуя, изображавшая самого правителя с макетом Константинополя в руках.
Что касается папы Урбана, то Михаил оказался прав в своих оценках. К Святому престолу были отправлены два посланца с извещением о восшествии Михаила на трон; с одного из них – согласно имеющимся источникам, которые, возможно, несколько преувеличивают, – заживо содрали кожу, второму же едва удалось спастись. Урбан, поощряемый Балдуином, настойчиво призывал к организации нового Крестового похода с целью отвоевания Константинополя для Запада. Венецианцы полностью поддержали его, но, к разочарованию Урбана, никто более не проявил особого энтузиазма. Во Франции король Людовик Святой рассудительно заявил, что целью Крестовых походов является борьба с неверными, а не с собратьями-христианами. Германия пребывала в состоянии смятения после произошедшей в 1250 г. смерти Фридриха II. Сын Фридриха, Манфред Сицилийский, мог бы откликнуться на призыв Урбана – союз с Римом, почти несомненно, позволил бы ему получить давно уже чаемое признание со стороны папы, – но Урбану такой альянс казался немыслимым. Он знал о непомерных амбициях короля Сицилии, и, даже если бы с его помощью удалось восстановить на константинопольском троне Балдуина, перспектива последующего возвращения долгов Манфреду представлялась папе слишком ужасной.
Ничего не приходилось ждать от генуэзцев, которых понтифик некоторое время назад отлучил от церкви за поддержку Восточной империи. Однако их сближение с Константинополем оказалось весьма непродолжительным. Летом 1263 г. недалеко от острова Спеце совместная византийско-генуэзская флотилия числом в 48 кораблей дала бой венецианской, насчитывавшей 32 боевых судна. Сражение закончилось унизительным поражением союзников. Не скоро генуэзцам удалось оправиться от этого разгрома и восстановить свои позиции в Восточном Средиземноморье, но еще важнее то, что они утратили доверие и уважение Михаила Палеолога, который платил генуэзцам за защиту византийских территориальных вод и ожидал более значимой отдачи от вложенных денег. Несколько недель спустя Михаил вообще отказался от услуг генуэзской флотилии и предложил ей возвращаться домой.