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

От генуэзцев нечего было ждать, так как папа недавно отлучил их от церкви за поддержку Восточной империи; однако их дружеские отношения с Константинополем долго не продлились: летом 1263 года у острова Спеце совместный флот из 48 византийских и генуэзских кораблей встретился с 32 византийскими судами. Стычка закончилась унизительно для генуэзцев, чей флот потерпел позорное поражение. Прошли долгие годы, прежде чем они снова стали силой в Восточном Средиземноморье, но что более важно, они лишились уважения Михаила VIII Палеолога, платившего им за патрулирование и требовавшего лучшей службы за свои деньги. Несколько недель спустя Михаил внезапно распустил остатки их флота примерно из 60 кораблей и приказал им возвращаться домой.

У императора были и другие причины для недовольства. Генуэзцы прибывали в Константинополь в таких количествах и торговали там настолько агрессивно, что стали угрожать национальному торговому сообществу и становились опасно непопулярны среди местного населения. На следующий год был раскрыт заговор, затеянный генуэзским подеста[89] в Константинополе Гульельмо Гуэрчио, собиравшимся предать Константинополь Манфреду Сицилийскому. Когда император предъявил Гульельмо неопровержимые доказательства, тот немедленно во всем сознался, после чего всех генуэзцев изгнали из города, и всего через три года после Нимфейского договора 1261 года союз с генуэзцами окончился катастрофой.

После разрыва с Генуей Михаил VIII Палеолог больше, чем когда-либо, нуждался в друзьях. Манфред его игнорировал, король Людовик был полностью поглощен своими делами. Оставался лишь сам папа римский, чья враждебность происходила не из личной неприязни, а лишь из естественного желания вновь видеть Константинополь подчиненным Риму. В то же время Михаилу было хорошо известно, что для папы гораздо предпочтительнее иметь на Босфоре греческого императора-еретика, чем короля Сицилии. Весной 1263 года грек по имени Николай, латинский епископ города Кротоне в Калабрии, отправился из Константинополя в Рим с письмом для папы, в котором содержались намеки на возможность церковного единства.