Утром 3 мая 32-пушечный фрегат «Саксесс» (капитан — Шадхэм Пид) и 14-пушечный бриг «Чалдерс» (капитан — Джеймс Коутс Кроуфорд) из эскадры вице-адмирала Кейта, патрулировавшие между Кадисом и Титуаном, обнаружили 5 испанских линейных кораблей, вышедших из Феролля. Англичане организовали наблюдение за испанцами и 11 мая обнаружили, что флот идальго на траверзе Порто соединился с отрядом Брюи. В этот момент «Саксесс» был обнаружен испанскими фрегатами, которые ринулись в погоню за дерзким англичанином, но тот смог уйти, скрывшись в темноте на фоне берега. «Саксесс», пройдя к Кадису, отрапортовал Кейту о случившемся, и 15 британских кораблей сразу же взяли курс на северо-запад. На следующий день в 8.30 утра Кейт обнаружил огромную вражескую эскадру из 33 (реально их было 30) линейных кораблей под прикрытием довольно большого числа фрегатов, двигающуюся на юго-запад. Французы прошли всего в 5–6 милях от англичан, мателот британского флагмана — 98-пушечный «Барфлер» — был ближе всех к союзникам и постарался сесть на хвост врагу, однако густой туман, опустившийся над морем, вскоре скрыл франко-испанский флот от Кейта
Меж тем Брюи задрейфовал неподалеку от Кадиса — он ждал выхода остальных испанских кораблей, но ветер не благоприятствовал идальго. 5-го числа французы миновали Гибралтар и вошли в Средиземное море. Кейт, узнавший, что французы и испанцы имеют в линии не менее 40 кораблей, ограничил свои действия тем, что спустился на траверз Гибралтара, преследовать лишь 15 линкорами такую силу было очень опасно. Всего к Брюи смогло присоединиться 15 испанских кораблей (из них четыре — 112-пушечные) под командованием лейтенант-генерала Массаредо. 21 мая союзный флот беспрепятственно прошел в Геную, где снабдил армию Моро припасами и солдатами. Через десять дней, приняв раненых, республиканцы взяли курс на родину. В это время англичане, напуганные численностью кораблей Брюи, концентрировали свои силы в Неаполе. Кейт и Нельсон считали, что задачей, поставленной перед таким крупным соединением, были деблокада Мальты и эвакуация армии Бонапарта из Египта, поэтому призвали в Неаполь даже русско-турецкую эскадру адмирала Ушакова (Ушаков решил все же базироваться на Корфу). Меж тем сами французы были уверены, что победа над русскими и австрийцами в Северной Италии делает блокаду Мальты британцами очень затруднительной, ведь в этом случае Нельсон и Кейт могли использовать в качестве полноценной базы только Гибралтар.
После выполнения поставленной задачи французская эскадра Брюи отправилась в Тулон, а Массаредо — в испанскую Картахену. Ни Кейт, ни Нельсон не преследовали союзников.
В апреле 1799 года на Мальте начался настоящий голод. Только за месяц умерли более 1000 человек, кэптен Болл выделил провизию для восставших из запасов эскадры, но этого было недостаточно. Французы увеличили поставки продовольствия на Мальту, и Болл прервать их не смог. Однако французы были в таком же положении, как и осаждавшие, поэтому не смогли организовать вылазки против неприятеля, хотя это могло бы полностью дезорганизовать восставших.
В конце месяца на острове ждали прибытия 30-го и 89-го полков с Менорки, но в это время Нельсон был извещен, что французский флот вырвался из Бреста, и их отправка была приостановлена. 26 линейных кораблей флота Океана под командованием адмирала Брюи сумели выйти из Бретани и направились в Средиземное море. На траверзе Кадиса к ним присоединилась испанская эскадра в составе 17 линейных кораблей. Англичане были в панике: они считали, что основной задачей Брюи были деблокада Мальты, захват Корфу, прорыв к Александрии и эвакуация в Италию армии Бонапарта. 5 мая французы и испанцы вошли в Средиземное море. В погоню вышла эскадра Кейта из 15 кораблей. Блокада с Мальты была снята (13 мая соединение Болла отозвали), в то время как русские силы начали собираться на Корфу.