Однако положение империи стало настолько критическим, что без союзников было все равно не обойтись. Война на два фронта приносила все новые поражения. Император умолял о помощи европейских королей и даже готов был идти на объединение с католической церковью, хотя разногласия двух ответвлений христианства, казалось, носили непреодолимый характер. «Именем Бога и всех христианских провозвестников, умоляем вас, воины Христа, кто бы вы ни были, спешите на помощь мне и греческим христианам. Мы отдаемся в ваши руки; мы предпочитаем быть под властью ваших латинян, чем под игом язычников. Пусть Константинополь достанется лучше вам, чем Туркам и Печенегам. Для вас должна быть так же дорога та святыня, которая украшает город Константина, как она дорога для нас», – писал Алексей в одном из своих посланий. Для вознаграждения император готов был пустить все неисчислимые богатства накопленные церковью, но Европа не отозвалась. В Константинополь прибыло лишь несколько сотен вечных искателей приключений – рыцарей.
Делать было нечего, и теперь уже византийские дипломаты оказались вынуждены в 1091 г. направиться к кипчакам как к единственной силе, способной спасти погибающую империю. Кипчакские ханы Боняк и Тугоркан откликнулись на предложение Алексея заключить союз, но вели себя крайне заносчиво, и при личной встрече со степными владыками в г. Энос императору пришлось пережить несколько крайне неприятных для себя и своего достоинства эпизодов.
И хотя союз был заключен, выяснилось, что Алексей боится своих союзников ничуть не меньше, чем печенегов, и под всевозможными предлогами избегает генерального сражения. В результате кипчакские ханы заявили: «До коих пор мы должны будем откладывать битву? Знай, что мы не будем ждать более; завтра с восходом солнца мы будем есть либо волчье мясо, либо баранье». После таких слов встревоженный византийский император, вовсе не желавший оказаться в роли «барана», наконец, решился перейти от слов к делу.
В битве при Лебурне объединенные силы греков и кипчаков нанесли полное поражение печенегам. Но то, что произошло после сражения, шокировало, казалось бы, ко всему привычных кипчаков, которых византийцы обычно презрительно именовали скифами. Празднуя победу, «цивилизованные» греки просто растерзали попавших в плен 30 тысяч печенежских женщин и детей. Напуганные невиданным зрелищем кипчаки, прихватив свою часть добычи, поспешили вернуться в родные кочевья. При возвращении домой кипчаки подверглись нападению венгров и были разбиты. Кипчакские ханы пытались уладить дело миром и потребовали от венгерского короля Владислава вернуть пленников, но были разгромлены еще раз.