Конвой двигался вдоль побережья Туниса. Наблюдатели сообщали об осветительных ракетах со стороны моря, вызвав опасение, что надводные силы противника охотятся на них. Одному из эсминцев померещились сигналы с берега, когда огибали мыс Бон, а в 01:12 11-я флотилия прошла так близко от берега, что обстреляла останки потерпевшего крушение «Хэвока» на мысе Рас-Мустафа, приняв их за вражеские корабли. На рассвете 15 июня британский конвой, двигавшийся на юго-восток на 12 узлах, находился в 25-30 милях юго-западнее острова Пантеллерия. До Мальты оставалось порядка 12 часов хода, что давало надежду на благополучный исход операции, когда в 05.20 (или чуть позднее) Харди перехватил радиограмму от одного из мальтийских самолетов: «...2 вражеских крейсерах и 4 эсминцах в пятнадцати милях к северу». Авторство этого сообщения неизвестно до сих пор. Первый патруль из пяти «Бофайтеров» 235-й эскадрильи в поддержку конвоя был поднят в 03:50 и находился в воздухе до 08:30, но информация о том, что он что-то обнаружил, отсутствует, зато пилоты отрапортовались о «стычке с МС.202 и повреждении Ju-88», чего не зафиксировано у немцев и итальянцев. Первый доклад об обнаружении конвоя и итальянской эскадры поступил от вылетевшего на поиск в 05.20 разведчика «Спитфайр» только после начала сражения: «Замечены два соединения, одно к северу, другое южнее, 25 миль от Пантеллерии в 225°. Оба соединения ведут бой».
Как бы то ни было, суда перестроились в две колонны с «Каиром» впереди. Эсминцы выдвинулись вперед - 11- я флотилия справа, 12-я флотилия слева, а минные тральщики увеличили скорость.
Хотя выход итальянских крейсеров 7-й дивизии из Палермо не остался незамеченным англичанами, они рассчитывали, что она движется на соединение с главными силами и не собирается действовать самостоятельно. Поэтому ее появление стало для кэптена Харди в значительной степени неожиданным. Увидев противника в 05:30 на фоне разгорающегося рассвета (наблюдатель «Бедуина» сообщил о вражеской эскадре как об «алжирских рыболовных судах»), Харди приказал 11-й флотилии флотских эсминцев коммандера Скэрфилда оставить свою позицию на не угрожаемом фланге конвоя, в то время как «ханты» и «Каир» принялись ставить дымзавесу. Он писал: «Мое намерение состояло в том, чтобы выиграть время и тянуть его в надежде на помощь ударной авиации с Мальты».
Сразу после обнаружения конвоя находившаяся в Кальяри итальянская 7-я дивизия крейсеров под командованием контр-адмирала Да Зара была приведена в боевую готовность и вскоре получила приказ на переход в Палермо, откуда удобнее было перехватить неприятельские суда на подходе к Мальте. В 16:00 13 июня «Савойя» и «Монтекукколи» с эсминцами 11-го дивизиона («Маэстрале», «Ориани», «Аскари» и «Джоберти») вышли в море и в 08:31 утра 14 июня прибыли в пункт назначения. Одна из британских подводных лодок у северо-западного побережья Сицилии заметила вышедшую из Кальяри вражескую эскадру, состоявшую из «2 крейсеров и 3 эсминцев», и ночью с Мальты на перехват вылетела группа из четырех «Веллингтонов», но из-за трудностей с освещением цели они были вынуждены вернуться, не сбросив торпеды. На следующий день самолеты-разведчики обыскали район между Сицилией и Пантеллерией, но никого не обнаружили.
По прибытию в Палермо, Да Зара провел совещание с командирами кораблей. Для выполнения поставленной задачи, помимо 11-го дивизиона эсминцев, ему был придан 14-й дивизион, состоявший из «Вивальди», «Дзено» и «Малочелло». В 20:05 «Эудженио ди Савойя» вышел из гавани, за ним следовали «Монтекукколи» и эсминцы. «Маэстрале» пришлось оставить в Палермо из-за аварии силовой установки, а вскоре на «Дзено» и «Джоберти» также возникли неполадки в машинах, и Да Заре пришлось отправить их назад. С крейсерами осталось всего четыре эсминца, поэтому на усиление эскадры Супермарина направила из Трапани «Премуду». Итальянское командование также направило три группы торпедных катеров к мысу Бон, но бурное море заставило их вернуться назад прежде, чем они увидели британские корабли.
В сумерках мальтийский фоторазведчик «Спитфайр» заметил итальянцев, выходивших из Палермо. К эскадре присоединился еще один эсминец. Однако к этому времени конвой, который вышел из Александрии 12 июня, попал в опасную зону, где его могли перехватить вышедшие из Таранто главные силы итальянского флота. Поэтому фоторазведчик с «двух крейсеров и двух эсминцев» был перенацелен на район к югу от Таранто. В 19:00 вице-маршал авиации Ллойд собрал всех пилотов Мальты вместе, чтобы объявить, что «два конвоя следуют к острову в попытке облегчить критическое положение с питанием. Последние подкрепления «Спитфайров», «Бофортов» и «Бофайтеров» находятся здесь, чтобы защитить корабли от вражеских атак». При этом наличные силы позволяли прикрывать конвой одновременно только четырьмя истребителями, чтобы обеспечить над судами непрерывный «зонтик».