Вскоре появился конкурент-претендент, утверждавший, что он является Алексеем II; он был первым из многих ему подобных, которые заполонили империю. Евстафий Солунский сообщает, что он был крестьянским парнем из Вагенетии (Воницы в Иллирии), которого бывший солдат, ставший монахом, по имени Алексей Сикунтин из Филадельфии подготовил к этой роли. До прибытия в Италию они оба путешествовали вдоль побережья Адриатики, завоевывая огромную популярность. В Палермо «подлинность» юноши была изначально скрыта, а затем информации об этом было позволено просочиться. Когда тот предстал перед королем, Алексей-виночерпий высмеял его, но группа генуэзских купцов, которые бывали в Константинополе, поручились за его подлинность. Король Вильгельм – какими бы ни были его личные сомнения – оказал ему императорские почести и предоставил ему сильную охрану для защиты от наемных убийц Андроника. Молодой человек не принял участия в последовавшей войне, но и Алексей Комнин виночерпий, и солдат-монах Сикунтин отправились вместе с норманнской армией.
Кого из двух претендентов поддерживала эта экспедиция, так и не стало ясно, так как настоящим намерением Вильгельма, как понимали все современники, было самому сесть на трон Византии; Евстафий даже утверждает, что он планировал передать кому-то Сицилию. Решение Вильгельма не принимать лично участия в походе, вероятно, должно было продемонстрировать обоснованность мнимого отсутствия его интереса. Его план не был беспрецедентным: в 1081 г. Робер Гвискар поддержал аналогичного претендента – лже-Михаила VII с не более благородными намерениями, чем были у Вильгельма II. Против плана Вильгельма высказались архиепископы Палермо и Мессины, но в ответ на их осторожные сомнения король сказал, что момент – самый подходящий: Алексей-виночерпий уверил его, что при его приближении начнется широкое восстание магнатов против жестокого Андроника, которое поможет и ему самому, и королю.
Приготовления Вильгельма II заняли первую половину 1185 г. Он захватил торговые суда, чтобы использовать их как транспорт, и запретил все поездки на Восток, чтобы помешать слухам достичь Константинополя. Слухи спекулировали на намеченной цели огромного войска: Майорка, Александрия или бывшие норманнские владения в Северной Африке; но расспросы короля о событиях в Константинополе не оставляли сомнений в его намерениях. Войско было очень большим; Евстафий узнал от друзей-латинян, что оно насчитывало восемьдесят тысяч человек, включая пять тысяч рыцарей, но, как и большинство оценок летописцев, эти цифры нельзя принимать буквально. Ибн Джубайр пишет, что в путь отправились три или четыре сотни кораблей; Евстафий утверждает, что двести кораблей осаждали Фессалоники; а Никита Хониат сообщает, что такое же их число позднее приблизилось к Константинополю.
Из-за метода набора солдат в армию качество норманнской армии было не самым лучшим. Вместе с наемниками Вильгельм завербовал в нее авантюристов всех национальностей, которые служили не за плату, а рассчитывали на трофеи. Аналогично флот включал пиратские корабли на той же основе. Присутствие таких элементов привело к неоднократному совершению преступлений во время оккупации Фессалоник и позднее фатально сказалось на дисциплине. Поведение западноевропейских вооруженных сил демонстрировало их крайнюю неотесанность: они презрительно относились к византийским предметам искусства и роскоши и неоднократно зло высмеивали православные религиозные службы. Однако их боевые качества были отличными.
Полководцами были граф Балдуин и граф Ришар Ачерра; последний позднее восстал против Генриха VI и пал от рук этого императора. Граф Балдуин, который не известен иначе, был главнокомандующим сицилийской армии. Никита Хониат изображает его хвастуном: «…[он] не был родом из благородной или известной семьи, но король ценил его за его военное искусство и облек его полномочиями главнокомандующего надо всеми, и он, кичась своими предыдущими победами над римлянами [византийцами], сравнивал себя со знаменитым Александром Македонским… и хвастался, что он совершил более великие подвиги, чем тот, за короткий период и без кровопролития». Евстафий восхваляет его щедрость и усилия по сохранению дисциплины во время оккупации Фессалоник. Адмиралом флота был граф Танкред из Лечче, который позднее стал преемником Вильгельма на троне Сицилии.