В самом деле, Берке решил не рисковать и на время отложил военные действия против ильхана. Ногай получил возможность реабилитироваться на другом фронте – балканском: Берке поручил ему деликатную миссию по освобождению из византийского плена бывшего сельджукского султана Изз ад-Дина Кей-Кавуса. Вероятно, направляя в этот поход именно Ногая, Берке полагал, что Ногай, имея владения на Балканах, сумеет использовать свои связи в этом регионе для успешного завершения операции.
Так и получилось. Ногаю даже не понадобились значительные ордынские силы: с помощью посулов или угроз он сумел убедить болгарского царя Константина Асена принять участие в походе со своей многочисленной армией. Болгарский царь, к которому Кей-Кавус неоднократно обращался за помощью, и сам разрабатывал планы по освобождению пленного султана и поэтому внимательно следил за событиями в Византии. Получив сообщение, что император Михаил VIII Палеолог находится в Фессалии и собирается возвращаться в Константинополь, Ногай и царь Константин замыслили дерзкий план: захватить императора в плен, и тогда освобождение султана оказалось бы проще простого.
Болгары, издавна воевавшие с Византией и хорошо знавшие местность, оказались хорошими проводниками. Они сумели скрытно провести войска Ногая и Константина в пределы Фракии, где ордынцы решили устроить засаду императору Правда, долго сохранять свои намерения в тайне им не удалось: воины Ногая, а за ними и болгары начали грабить местное население, в результате чего по всей округе разнеслись слухи о вторжении врага, которые, в конце концов, дошли и до императора. Михаил VIII, отрезанный от столицы и своих основных сил, попал в крайне затруднительное положение. Один раз он оказался на расстоянии дневного перехода от войск Ногая и едва не попал в плен. С большим трудом императору удалось добраться до города Гана, где он, к своему огромному облегчению, увидел в порту две генуэзские галеры и решил добраться до столицы морем.
Не сумев пленить императора, Ногай вернулся к первоначальному плану и двинул свои объединенные силы к городу Эн, в котором Михаил VIII держал султана Кей-Кавуса. Осадив его, Ногай направил в город посланцев, через которых передал местным жителям, если те не выдадут султана, он возьмет город и истребит всех поголовно. Находившиеся при султане императорские стражники, опасаясь наказания за утрату пленника, намеревались оказать сопротивление и были готовы, в крайнем случае, даже умертвить султана, но не отдавать его ордынцам. Однако население, решив использовать имеющийся шанс сохранить жизнь и имущество, заставило их выдать Кей-Кавуса. Как только султан покинул город и оказался в лагере Ногая, ордынский полководец приказал немедленно сниматься и уходить: он также не горел желанием завершить столь удачный и прибыльный поход встречей с императорскими войсками, которая неизвестно чем могла кончиться. Ногай поступил совершенно правильно: два дня спустя после его ухода на рейде Эна оказался императорский флот.
