Кадиса 24 мая. Прибытие 8 других линкоров из Англии позволило Сен-Винсенту отделить столь крупные силы. По пути к Трубриджу присоединились «Одэшиус» 74 и «Леандр» 50, так что Нельсон неожиданно оказался командующим эскадры, состоящей из тринадцати 74-пушечных линкоров: «Вангард», «Орион», «Александр», «Каллоден», «Голиаф», «Зилоус», «Одешиус», «Тесей», «Минотавр», «Дефенс», «Беллерофон», «Маджестик» и «Свифтшур», а также 50-пушечного «Леандра» и 16-пушечного шлюпа «Мутин».

Не имея никакой информации о местонахождении французов, Нельсон повел свой флот на восток и юг вдоль итальянского побережья. 14 июня, находясь возле Эльбы, он получил информацию из вторых рук о том, что противника видели у западного побережья Сицилии идущим на восток. Нельсон сразу же послал Трубриджа на «Мутине», чтобы узнать новости в Неаполе и выяснить, на какой прием он может рассчитывать в неаполитанских портах. 18-го «Мутин» снова соединился с главными силами флота к югу от Неаполя. Трубридж узнал, что французы ушли на Мальту, а все сицилийские губернаторы готовы оказать британцам любую помощь. Надеясь перехватить противника на Мальте, Нельсон повел свой флот через Мессинский пролив, а оттуда в южном направлении. 22 июня, проходя мимо мыса Пассаро, он услышал, что Мальта сдалась еще 15-го и на следующий день французы ушли. Обе эти даты были неверными. Капитуляция имела место 12-го, а французы оставались до 19-го, но суть информации была абсолютно правильной: французы взяли Мальту и исчезли.

Ходили слухи, что местом их назначения была Сицилия, но Нельсон и четыре его капитана, мнение которых он выяснил, считали, что в этом случае о них уже бы поступили какие-то новости. Так что, вероятнее всего, они держат курс на Египет. Нельсон сразу приказал идти в Египет и по прибытии в Александрию 29 июня испытал глубочайшее разочарование, обнаружив, что там никто даже не слышал о французах.

Нельсон поступил в противоположность тому, что Бонапарт и Бруе сделали месяцем раньше. Они ждали конвой из Чивитавеккьи, когда он фактически был впереди них. А он поспешил за французским флотом, когда тот был позади него. Покинув Мальту 19-го, французы дошли в восточном направлении до Крита, а потом взяли курс на юго-восток. А Нельсон от мыса Пассаро направился сначала на юго-восток, а потом примерно на ост-зюйд-ост, то есть оказался значительно южнее курса французов. Он заметил два французских фрегата 22-го, но, поскольку у него самого фрегатов не было, он не смог организовать преследование. Даже не подумав о том, что он мог попросту обогнать французов, Нельсон не стал терять время в Александрии, и его флот пошел на север, к побережью Малой Азии. Затем он прошел вдоль южной стороны Крита, и, наконец, 19 июля британский флот бросил якоря у Сиракуз на Сицилии, все еще не имея никакой информации о местонахождении противника.