Но Вильгельм Сицилийский вовсе не собирался сдаваться. Он проиграл первый раунд, но затем стряхнул с себя привычную апатию, и кровь его вскипела. В начале 1156 года его армия и флот встретились в Мессине: греков, сторонников папы и мятежников нужно было атаковать одновременно с суши и с моря. В апреле его армия перебралась на материк, а флот поплыл на юг через проливы и повернул к Бриндизи, который тогда находился в осаде византийцев. Когда Вильгельм перешел в наступление, греки увидели, что их мятежные союзники один за другим испаряются. Наемники, как водится, в самый критический момент затребовали непомерного повышения жалованья, а получив отказ, дружно исчезли. Граф Лорителло дезертировал, его примеру последовали многие его соотечественники. Михаил Палеолог умер; Иоанн Дука обнаружил, что противник безнадежно превосходит его численностью. Его, других выживших византийцев и тех немногих норманнских мятежников, которые еще не сбежали, взяли в плен. Греческие корабли захватили вместе с большим количеством золота и серебра. За один-единственный день, 28 мая 1156 года, все достижения прошлого года в Южной Италии сошли на нет. Вильгельм Сицилийский обошелся со своими греческими пленниками по законам военного времени, а к своим мятежным подданным без всякой жалости. Доблестно сопротивлявшийся Бриндизи он пощадил; капитулировавшему Бари пришлось поплатиться. Жителям дали два дня на спасение имущества, после чего город был уничтожен вместе с собором. Осталась стоять лишь церковь Святого Николая.

Стало ясно, что пришло время для радикальных перемен в политике империи. Если Мануил не мог вернуть утраченные итальянские провинции силой оружия, то этого не мог сделать и Барбаросса; однако Фридрих наверняка организует новый поход и может даже свергнуть Вильгельма с трона. В таком случае, с учетом того, что он намерен объединить две империи, не сделает ли он своей следующей целью Византию? Вывод прост: выскочка Вильгельм Сицилийский гораздо предпочтительнее Фридриха. Придется достичь с ним какого-то соглашения. Летом 1157 года Мануил отправил в Италию нового, весьма способного посла – Алексея, сына главного доместика Аксуха. Ему были даны указания, подобные тем, что прежде получил Михаил Палеолог: он должен был якобы связаться с потенциальными мятежниками, найти наемников и в целом вызвать к себе неприязнь; второй же его задачей было установление тайных сношений с Вильгельмом Сицилийским и обсуждение условий мира. Эти две цели не настолько противоречили друг другу, как может показаться на первый взгляд: чем более яростной будет предварительная схватка, тем более благоприятными для Византии могут быть условия, предложенные Вильгельмом.