Когда Нельсон снова вернулся к Тулону, порт оказался пуст. Армада Бонапарта, состоящая из сотни войсковых транспортов и судов снабжения в сопровождении 13 линейных кораблей и 7 фрегатов вице-адмирала Брюэса, который держал флаг на 120-пушечном «Ориане», незаметно вышла в море, воспользовавшись штормом. Нельсон знал ничуть не больше, чем в тот день, когда отделился от Сент-Винсента со своими 3 линейными кораблями. Теперь ему предстояло, не имея легких судов, отыскать противника, который растаял за горизонтом и мог направиться куда угодно — на запад в Атлантику, на восток в Италию, Египет или Левант. Решение, которое предстояло принять Нельсону, имело решающее значение для исхода всей войны. Если он направится на восток и ошибется, противник сумеет прорваться в Атлантику. При этом появлялась опасность, что французы смогут ускользнуть и от флота Сент-Винсента, находившегося возле Кадиса.
Тем временем Сент-Винсент получил директиву Адмиралтейства с приказом послать 12 линейных кораблей в Средиземное море, «чтобы расстроить намерения Тулонского арсенала, каковы бы они ни были». Этим флотом мог командовать сам Сент-Винсент, или поручить это «кому-либо из адмиралов». К директиве было приложено личное конфиденциальное письмо лорда Спенсера, который просил Сент-Винсента не брать на себя командование экспедицией. «Я думаю, что почти необходимо предложить вам отдать эскадру под командование сэра Г. Нельсона, знакомство которого с этой частью света, а также его активность и предусмотрительность, делают его особенно подходящим для выполнения этой задачи».
5 июня «Ла Мутин» принес Нельсону, стоящему у мыса Сиси возле Тулона со своими кораблями, известие, что к нему идут 11 линейных кораблей. Через 2 дня капитан Трубридж привел эти подкрепления. Теперь Нельсон командовал флотом, состоящим из 13 74-пушечных кораблей: «Вэнгард», «Орион», «Александер», «Куллоден» (Трубридж), «Тезеус» (Миллер), «Минотаур» (Луис), «Свифтшур» (Хэллоуэлл), «Одейшиес» (Гулд), «Дифенс» (Пейтон), «Зиэлес» (Худ), «Голиаф» (Фоули), «Маджестик» (Весткотт) и «Беллерофон» (Дарби). Нельсон также имел 50-пушечный корабль «Линдер» (Томпсон) и 16-пушечный бриг «Мутин». Но капитан Хоуп и его фрегаты остались в Гибралтаре.
Приказ Сент-Винсента предписывал Нельсону отыскать, «захватить, потопить, сжечь или уничтожить» французский флот. Сент-Винсент предположил, что целью противника будет «либо атака Неаполя и Сицилии совместно с наступлением армии к побережью Испании, чтобы вторгнуться в Португалию, либо прорыв через Гибралтар, чтобы проследовать к берегам Ирландии». В этом не было ничего нового. Сент-Винсент даже не упоминал Египет. Специальное напоминание, что он должен принять особые меры, чтобы не допустить бегства противника на запад, делало положение Нельсона особенно трудным.
Ему не оставалось ничего иного, как попытаться любыми способами раздобыть сведения о противнике. «Мутин» был сразу послан осмотреть бухту Теламон на побережье Италии, так как Нельсон предположил, что там могут встретиться французы, вышедшие из Тулона, и эскадра из Генуи. Бухта оказалась пуста. Уже наполовину убежденный, что целью Бонапарта является Египет, Нельсон повел флот на юг к Неаполю. 14 июня возле Эльбы адмирал получил сведения, которые подтвердили его подозрения. Тунисский корабль сообщил, что некое греческое судно видело французский флот у северо-западного побережья Сицилии. Французы двигались на юг. Эта неопределенная информация позволила Нельсону предположить, что французы обойдут остров с юга. Он написал графу Спенсеру: «Если они обойдут Сицилию, я полагаю, они попытаются реализовать свой план захвата Александрии».
17 июня Трубридж помчался в Неаполь на «Мутине», чтобы попытаться вырвать у короля фрегаты, лоцманов и провизию для флота. Трубридж присоединился к Нельсону возле Искии без фрегатов, но с разрешением пользоваться неаполитанскими портами и донесением сэра Уильяма Гамильтона, британского посла в Неаполе. Он утверждал, что французы направились к Мальте. Сразу после этого Нельсон, рассчитывая перехватить французов возле Мальты, отправил письмо великому магистру Мальтийского ордена, предлагая собрать корабли, чтобы они присоединились к британскому флоту, когда тот подойдет к острову. 20 июня в Мессине он нашел местных чиновников страшно испуганными. Они не желали помогать англичанам и отказывались сообщить какие-либо сведения. Взбешенный Нельсон написал сэру Уильяму Гамильтону: «Зато французскому послу разрешено отправлять корабли, чтобы сообщить своему флоту о моем прибытии, составе флота и пункте назначения. Теперь мне не захватить их врасплох, они будут готовы сопротивляться». Еще больше осложняло ситуацию сообщение британского консула, что Мальта сдалась французам. Через 2 дня, примерно в 35 милях юго-восточнее мыса Пассаро «Мутин» встретил генуэзский бриг, который сообщил, что французский флот еще 16 июня покинул Мальту, направившись, «как предполагают, к Сицилии».