После этого Берке изъявил готовность послать в Египет в качестве поддержки несколько небольших военных отрядов (от 200 до 1300 чел.). Тогда Бейбарс отважился вступить в переговоры с вассалами ильхана атабеками[91] Фарским (в Ширазе)[92], Большого и Малого Луристана[93], а также с вассалом иранского хана в северной части сирийской пустыни, имевшим арабские корни. Целью этих переговоров являлся подрыв власти Хулагу изнутри, однако они каких-либо ощутимых результатов не принесли.

Вполне возможно, что это стало следствием инцидента, который на долгое время охладил отношения Бейбарса с Берке и сделал невозможным согласование совместных военных действий. Связь между Александрией и Крымом из-за расклада политических сил могла осуществляться только морским путем и с согласия Константинопольской империи, в которой в 1261 году вновь воцарился Михаил VIII из династии Палеологов[94].

Падение Латинской империи[95] лишило западноевропейские страны одного из их важнейших оплотов на Востоке, а поскольку Бейбарс рассматривал государства крестоносцев в Сирии преимущественно как вражеские, то он приветствовал победу Михаила VIII. Вскоре после восхождения на трон Палеологов с мамлюкским султаном был заключен договор, который обезопасил свободный проезд послов Бейбарса, а также прохождение его товаров, в том числе и рабов, через морские проливы. Вероятно, что восточноримский император принимал проезжих посланцев султана и кыпчакского хана и сообщал через своих посыльных соответствующей стороне об их прибытии.

Впрочем, Михаил не был готов, да и не имел такой возможности, принять однозначно сторону Бейбарса (и Берке тоже). Это означало бы демонстрацию позиции против Хулагу, успехи которого в Малой Азии представляли собой тогда серьезную угрозу для Византии в Азии. Между Константинополем и Тебризом, резиденцией ильхана, постоянно сновали посланцы. Даже после уплаты дани Хулагу за Трапезунд[96], что должно было удовлетворить ильхана, император считал для себя правильным установить с ним более тесные отношения. Когда в начале лета 1263 года по пути в Александрию в Византии появились послы Золотой Орды, Михаил послал вместе с ними своего собственного представителя, которому вменялось оправдать поступки своего суверена в глазах Бейбарса.

В то время с Каиром более тесные отношения установила и Генуя. Оба государства являлись противниками венецианцев, главного опорного пункта Латинской империи и одновременно друзьями византийского правителя. Кроме того, Генуя нашла теплый прием у кыпчаковских властей в Крыму.

Осенью 1263 года через византийские владения проезжала ответная делегация Бейбарса к Берке, но Михаил был занят в войне с западными странами («франками») и в Константинополе отсутствовал. Однако он не смог отказаться от встречи с послами и принял их в крепости, в которой на тот момент находился. В ней посланцы султана наткнулись на посольство Хулагу. Чтобы избежать огласки своих переговоров с ильханом, император неправомерно отправил египетских посланцев назад в Константинополь и продержал их там почти два года. Однако это не помогло. Берке и без того прознал про контакты между Михаилом и Хулагу. В результате удержание египетских послов послужило для него только удобным предлогом для воинственных действий.

К этому следует добавить еще кое-что. Палеолог содержал у себя при дворе в Константинополе, правда под легким арестом, сбежавшего к нему римско-сельджукского султана Из-ед-Дина. Из-ед-Дин и, видимо, его брат Руки ад-Дин Кылыч-Арслан IV попросили Берке вмешаться и вызволить узника из его незавидного положения. Это было как раз то, что хан Кыпчака мог использовать наилучшим образом, чтобы наказать Михаила VIII за его тесные отношения с Хулагу и в противовес ильхану путем вмешательства в дела Малой Азии заявить о своих притязаниях на главенство в данном регионе. Летом и осенью 1264 года он послал Ногая во Фракию, куда под предлогом необходимости встретиться с императором, стоявшим там с войском, отравился и Из-ед-Дин. Ногай связался с дунайскими булгарами, которые, пользуясь этим случаем, вновь тесно примкнули к Орде, и создал благодаря им императору такую угрозу, что тот был вынужден спасаться бегством и, чтобы вернуться в свой родной город, плыть на кораблях. Ногай окружил византийские войска в крепости Айнос, в которой находился римско-сельджукский султан. После длительной обороны гарнизон сдался. Осада была снята, а Из-ед-Дин отправился в Сарай, где Берке принял его весьма дружественно и на длительное время оставил в своем окружении.