Однако зимой появился новый враг: эпидемия (вероятно, тиф), которая не щадила никого. К весне 1085 года умерли 500 нормандских рыцарей, а большая часть армии утратила боеспособность. Сам Роберт сохранял бодрость и уверенность, но в середине лета, поплыв на захват Кефалонии, он почувствовал, что страшная болезнь настигла и его. Корабль бросил якорь в первом же безопасном месте – в заливе, который и сегодня называется Фискардо. Здесь Гвискар умер 17 июля 1085 года; его жена Сишельгаита была с ним рядом. Ему было 68 лет. За последние четыре года он видел, как при его приближении бегут императоры Востока и Запада; он своей рукой вернул на престол одного из величайших пап Средневековья. Если бы он прожил еще несколько месяцев, Алексей Комнин мог бы оказаться одним из краткосрочных византийских правителей, а может быть, и последним.

Империя избавилась от непосредственной опасности, но никогда не находилась в безопасности подолгу. Нормандцы временно сошли со сцены, но на их место пришли печенеги. За последние двести с лишним лет они оказались самым алчным и жестоким из варварских племен. Весной 1087 года огромное войско печенегов вторглось в империю; три года спустя оно стояло неподалеку от Константинополя. Алексей был вынужден прибегнуть к одному из древнейших дипломатических трюков – заручиться поддержкой одного племени в войне против другого. На этот раз он обратился к половцам. У них не было серьезных раздоров с печенегами, но они охотно откликнулись на его призыв. Половцы прибыли поздней весной, и в понедельник 28 апреля 1091 года два войска встретились у Левуниона в устье реки Марицы.

В произошедшей на следующий день битве печенеги, чьи жены и дети по традиции последовали за ними на войну, были почти полностью истреблены. Нескольких пленных оставили в живых и взяли на службу, однако большинство погибло во время массовой резни. Ни византийцы, ни половцы не вышли из этого боя с честью, однако битва при Левунионе стала самой яркой победой, одержанной византийской армией со времен Василия II. Она не только освободила империю от печенегов на ближайшие тридцать лет, но и преподала другим племенам хороший урок. Что еще важнее, она закрепила положение императора: он наконец доказал, что способен восстановить хотя бы часть былого величия Византии. Василевс, который через несколько дней после битвы гордо ехал по улицам Константинополя, мог смотреть в будущее так, как это не удавалось ему за все десять лет с восшествия на престол, – с уверенностью и надеждой.

Примерно к концу 1094 года Алексей Комнин принял послов из Рима. Папский престол уже шесть лет занимал Урбан II, который очень старался улучшить взаимоотношения между Константинополем и Святым престолом. Улучшать требовалось многое: после восшествия Алексея на трон папа Григорий VII отлучил его от церкви, а когда император узнал об альянсе папы с ненавистным герцогом Апулии, понтифик упал в его глазах еще ниже. Папа, в свою очередь, с таким же ужасом узнал, что Генрих IV получает плату от Алексея, и ко времени смерти Григория ситуация была хуже, чем когда-либо. Когда три года спустя на папский престол взошел Урбан, он начал примирение с того, что отменил отлучение Алексея, а тот в ответ открыл все латинские церкви в Константинополе, закрытые ранее по его приказу. Император и понтифик обменивались письмами, и разрыв постепенно уменьшался; ко времени приезда папских послов в Константинополь император и папа вновь были в дружеских отношениях.