Грабительская политика правительства в отношении восточных областей дорого обошлась Византийскому государству. Местное население все чаще предпочитало входить в контакты с турками и переселяться в их области. Оборона восточных границ империи была полностью дезорганизована — акриты уклонялись теперь от несения пограничной службы, перебегали к туркам. Турки по большей части безнаказанно переходили границу империи и захватывали византийские области. Им удалось овладеть важным опорным пунктом византийцев — городом и крепостью Траллы, который был разрушен до основания, а его жители перебиты. Процесс проникновения турок облегчался и тем, что все помыслы Михаила Палеолога были устремлены на запад, где его вожделенной целью было окончательное изгнание латинян. Военные экспедиции на восток посылались лишь эпизодически, и вся восточная граница империи в годы пребывания Михаила VIII у власти по сути дела была открыта для турок18.
Международное положение Византии было сложным. Падение Латинской империи явилось тяжелым ударом для многих государей Европы. Были затронуты интересы ряда стран, но в первую очередь был нанесен ущерб престижу папского престола, постоянного защитника латинских императоров Константинополя. Существенно пострадали и позиции Венеции, которая после Нимфейского договора потеряла господствующее положение в торговле в бассейне ВосточногоСредиземноморья и на Черном море.
Новый папа Урбан IV (1261—1264), вступив на престол, сразу же начал предпринимать меры против Византии, потребовав от Генуи разорвать союз с Михаилом Палеологом. Поскольку генуэзцы отказались, последовали отлучение от церкви правительства Генуи и папский интердикт на все население республики. Венеция поступила еще более решительно, послав с благословения папы флот против союзных эскадр Византии и Генуи. Сначала союзникам сопутствовал успех. Они заняли ряд островов Архипелага, захватили несколько венецианских кораблей. В руках Михаила оказался большой для того времени флот, насчитывавший до 60 галер. К этому времени вернувшийся домой из плена Гийом Виллардуэн был освобожден папой от клятвы, данной Михаилу VIII, и отказался выполнить условия договора о передаче Византии крепостей на Пелопоннесе. Император стал готовить туда военную экспедицию. Но ее пришлось отложить. Венецианцы разбили генуэзский флот в морском сражении при Сетте Поцци (1263 г.), применив хитроумную тактику морского боя. Вслед за тем последовало и политическое расхождение между Михаилом VIII и генуэзцами, воспротивившимися намерениям византийского императора идти к Пелопоннесу. Генуя не рискнула выступить против Гипома, пользовавшегося расположением Урбана IV, боясь еще более обострить и без того опасный конфликт с папской курией. Генуя склонялась к примирению с Римом, чему немало способствовали политика Сицилийского королевства и угрожающее соседство Карла Анжуйского. Разрыв Византии с Генуей стал неизбежным после измены главы генуэзской колонии в Константинополе Гильельмо Гверчи, который в союзе с тайными агентами сицилийского короля Манфреда Гогенштауфена строил планы передачи города латинянам19. После раскрытия заговора Михаил VIII изгнал генуэзцев из Константинополя, нанеся тем самым тяжелый удар генуэзской торговле, хотя в Галате они удержались.