Немногочисленный, а потому мобильный папский флот во главе с Колонной принялся действовать сразу после формирования Священной Лиги. Получив всевозможные благословения, Маркантонио Колонна покинул 15 июля Рим и отправился в Чивитавеккью — главный порт Папского государства. Там его ожидала часть солдат и моряков. Римскую эскадру встречал племянник папы Пия V, семья главнокомандующего и даже Орсини — заклятые враги рода Колонна. На берегу собралась вся римская аристократия, что являло собой поистине впечатляющее зрелище. Сюда же прибыли двадцать пять швейцарских гвардейцев и сто восемьдесят солдат пехоты, выделенных папой из гарнизона.
Двенадцать боевых галер, посланных великим герцогом тосканским, прибыли в Чивитавеккью с целым войском флорентийских дворян на борту. На многих аристократах была надета форма процветавшего тогда флорентийского религиозного ордена рыцарей Святого Стефана. Остававшимся в гавани кораблям Колонна приказал плыть в Мессину сразу же по завершении приготовлений. 21 июня он с двенадцатью галерами покинул Чивитавеккью и двинулся к Неаполю, где находился очередной порт для захода эскадры.
В порт Неаполя они вошли 24 июня. Условились, что эскадра Колонны будет ждать в Неаполе дона Хуана, следовавшего из Испании. По прибытии главнокомандующего папский флот проследовал бы дальше в Мессину вместе с главной силой союза — испанской эскадрой.
Колонна привез в Неаполь благословенный стяг Священной Лиги, который при более благоприятных обстоятельствах папа должен был лично вручить дону Хуану. И пока герцог австрийский не принял этот флаг, он не мог официально считаться главнокомандующим объединенного флота.
Тем не менее Колонна так и не дождался дона Хуана. Испания, господствовавшая на всем юге Италии от Неаполя до Сицилии, поместила своего вице-короля как раз в Неаполе. Когда Колонна поинтересовался у него о причине опоздания дона Хуана, вице-король не смог ответить, ибо сам ничего не знал.
Колонна, пусть и не очень одаренный в военном плане, но очень преданный, с тем же усердием, что и Пий, боролся за создание единой армады. Поэтому после трех недель ожидания в Неаполе он решил, что папской эскадре следует самостоятельно отправляться в Мессину. Благословенный стяг он передал вице-королю, и 15 июля его эскадра отчалила от Неаполя. Она двинулась через Тирренское море на юг, а вечером 30 июля вошла в гавань Мессины.
Венецианская флотилия под командованием Веньеро прибыла туда неделей раньше. Мессина расположена на восточном побережье Сицилии, прямо напротив итальянского полуострова, от которого ее отделяет узкий, но порожистый пролив. И хотя венецианская эскадра прибыла первой, ее путь был нелегким. По дороге сюда им пришлось немалым пожертвовать.
Еще до того как основная османская флотилия покинула порт, турецкие сановники приказали Улудж-Али развернуть партизанскую войну против венецианского флота. Улудж-Али, итальянец по происхождению и христианин в прошлом, отправил двенадцать высокоскоростных галер в сосредоточенную атаку против венецианских судов, следовавших на помощь Кипру. Будучи пиратом, он знал Средиземноморье как свои пять пальцев и передвигался крайне быстро на небольших судах. Когда все думали, что он все еще около Кипра, его неожиданно замечали в окрестностях Родоса. Мародерствуя несколько дней у южного берега Крита, Улудж-Али вдруг появлялся в водах у Мальты.
А еще он был отважен. Ему каким-то образом удалось потопить три крупных венецианских парусника, когда те по пути на Кипр остановились в открытом море. Вездесущее бдение турок на море постоянно препятствовало спасательной венецианской эскадре, как только та отплыла на восток от Крита. Однако даже Улудж-Али был не в силах контролировать всю Адриатику. Венецианские корабли размещались как на Корфу, так и около Крита.
Поэтому для Венеции было разумным временно оставаться на Корфу и Крите. Но опаздывавшие в Мессину союзные эскадры задерживали отплытие всей армады. И венецианскому адмиралу Себастьяно Веньеро пришлось сделать нелегкий выбор.
Он решил отправляться в Мессину, взяв с собой единственную корфиотскую эскадру. Критской эскадре он приказал также немедленно плыть в Мессину, как только она получит соответствующий приказ.
Этот шаг стоил ему непомерно дорого: в результате воды от Корфу до Крита остались фактически неприкрытыми. Но Венеция не могла поступить иначе. Веньеро взял с собой в Мессину пятьдесят восемь боевых галер и три галеаса. Он ожидал, что вскоре туда прибудет и Марко Квирини с шестьюдесятью кораблями.
Можно догадаться, каким было настроение у Веньеро, когда Колонна, опоздав на целую неделю, наконец-то прибыл в порт. Когда же венецианский адмирал узнал, что корабли задержались, так как дон Хуан не явился, ярости его не было предела.
Тридцатишестилетний Маркантонио Колонна скорее походил на придворного подхалима, нежели на главнокомандующего. Был он худощав, низенького роста, уже начинал лысеть. Его чересчур большие глаза оставляли впечатление, будто этот человек постоянно болел в детстве.
