11 августа Гарсия де Толедо созвал военный совет, на котором, после бурных обсуждений, было решено оставить суда, погрузить на 60 лучших галер как можно больше солдат и попытаться высадить их без боя. Христиане были убеждены, что в распоряжении турок более ста галер, пригодных для использования. Правда, вероятнее всего, единовременно могли выйти в море не больше 50 кораблей, причем на всех не хватало людей и амуниции. При встрече существовала вероятность нанести им поражение, но если сражения удастся избежать – тем лучше. Решение было хорошим, но его исполнение опоздало. Только 21 августа флот наконец вышел из Мессины в Сиракузы, и 25-го числа он подошел к Мальте, доставив 10 тысяч человек.
Следующие две недели были полны ошибок и разочарований. 27-го флот покинул мыс Пассаро и направился к острову Лампедуза, расположенному в 70 милях к вест-норд-весту от Мальты, но попал в полосу сильного восточного ветра, который отнес корабли до Фавиньяны – острова, расположенного у западной оконечности Сицилии, где 29-го они бросили якоря. Тем временем Дориа, который вышел из Сиракуз 23-го, чтобы установить связь с гарнизоном Гозо и ждать главные силы флота у Лампедузы, потерял несколько человек и сам был ранен в стычке с небольшим турецким кораблем, и вернулся в Ликату. После короткого визита в Трапани флот 2 сентября снова отошел от Фавиньяны, миновал соседний остров Линоза, расположенный рядом с Лампедузой, и оттуда направился к Гозо. По пути корабли разделились, и хотя 4-го они снова соединились, вице-король решил вернуться на Сицилию, так и не сделав попытки высадиться на Мальте. Прибыв к Паццало 5 сентября, он соединился с Дориа, который прибыл к Линозе в надежде найти его там. Тот сообщил, что в направлении Гозо все чисто, и стал настаивать на возвращении. Соответственно, 6 сентября флот вышел с Сицилии в третий раз и уже на следующий день, рано утром, высадил войска в бухте Мелекка, что на северо-западной оконечности острова Мальта. Как только это было сделано, галеры снова вернулись на Сицилию, чтобы взять еще четыре тысячи человек. Но чтобы удостовериться в том, что все заинтересованные лица знают, что прибыла помощь, они прошли мимо Большой бухты и дали залп из бортовых орудий. Около 80 турецких галер вышли из Карантинной гавани, возможно, с намерением вступить в бой, но к тому времени, как они оказались в море, христианский флот уже был вне досягаемости.