С союзниками, однако, обстояло печально. Грекам стало не до Леванта, поскольку в 1258 году скончался император Феодор I Комнин, оставив восьмилетнего сына Иоанна, опекуном которого назначил патриарха Арсения, а регентом своего приближенного Георгия Музалона. С учетом как истории и традиций Византии, так и состояния дел в моменте, шансы наследника на сохранение власти и жизни оценивались как нулевые, а вопрос о реальном правителе встал сразу после смерти предыдущего василевса. Спустя девять дней после которой, во время поминок, Георгия Музалона, с братьями и окружением, атаковали прямо в церкви неустановленные бойцы и положили на месте.
После раунда напряженных интриг и переговоров, место регента досталось ранее упоминавшемуся Михаилу Палеологу, зятю покойного василевса, авторитетному полководцу и лидеру военной партии, получившему титул деспота — второй после императорского. Михаил начал выстраивать вертикаль власти, отстранять несогласных и раздавать обещанные бонусы союзникам, а воевать с Хулагу до завершения этого процесса не собирался — и оставить столицу, возглавив армию, и поручить кому-то войска, выглядело одинаково рискованно.
Палеолог оказался не только полководцем, но и дипломатом, причем играющим стратегически. Он заключил договор с Берке (по некоторым данным, впрочем, готовившийся еще при предшественниках обоих правителей), ставший одним из ярчайших образцов византийской внешней политики. С формальной стороны, василевс обязался выплачивать правителю Золотой Орды (
Союз предусматривал помощь в случае нападения Хулагу или самого Мунке — фактор важный для внутренней устойчивости обоих правителей и сдерживания восточного соседа. Стороны признали границу в Валахии «по факту», сняв риски войны на этом фронте. Пограничные стычки и набеги не прекратились, но серьезных столкновений здесь долгое время не было. Взамен Константинополь прекратил поддержку венгров (с которыми начались пограничные споры) и князя Галицкого (по мнению греков, излишне сблизившегося с европейцами).
Но главной темой была экономика. Черное море к тому времени стало венецианским. Республика Св. Марка, укрепившись в новом регионе умело играла на противоречиях между ромеями и татарами, добилась привилегий от обеих сторон, и к концу 1250-х годов поступлений от черноморской торговли практически лишились и Сарай, и Константинополь. Изгнать венецианцев, успешно вписавшихся в рынок, а в ряде сфер его переформатировавших, без потерь уже не выходило, да и доверие между греками и татарами было не настолько велико, чтобы уйти от посредника, к тому же игравшего в интересах Михаила и Берке и за пределами региона. Потому контролирующие доступ к морю лица предпочли влияние посредника
Для Леванта все эти глобальные политические сдвиги никакой пользы не несли. Усиление греков даже сыграло негативную роль — король Киликии Хетум I, ища поддержки против греков и сочтя Сирию обреченной, начал сближение с Хулагу.