С началом войны с Турцией было решено отправить в Средиземное море эскадру в составе семи кораблей («Европа», «Святослав», «Св. Евстафий», «Три Иерарха», «Св. Иануарий» и «Три Святителя», из которых «Святослав» был 80-пушечный, а остальные — 66-пушечные). Кроме того, в составе эскадры был фрегат «Надежда Благополучия», 10-пушечный бомбардирский корабль «Гром», четыре пинка (в ряде документов они именовались транспортами) и два пакетбота (посыльных судна) — «Летучий» и «Почталион».
Эскадра получила название «обшивная», поскольку корпуса всех ее судов были обшиты снаружи дополнительным рядом дубовых досок с прокладкой из овечьей шерсти, чтобы подводную часть не источил морской червь, как это произошло с «Надеждой Благополучия». Естественно, что обшивка уменьшала скорость хода и увеличивала осадку судов.
По совету Мордвинова и общему мнению Адмиралтейств-коллегии Екатерина предложила командование эскадрой Г.А. Спиридову, тогда еще вице-адмиралу. Екатерина схитрила — присвоила Спиридову звание полного адмирала и назвала его первым флагманом флота.
В рескрипте, подписанном Екатериной и врученном Спиридову, говорилось: «…Провезти сухопутные войска с парком артиллерии и другими военными снарядами для содействия графу Орлову, образовать целый корпус из христиан к учинению Турции диверсии в чувствительнейшем месте; содействовать восставшим против Турции грекам и славянам, а также способствовать пресечению провоза в Турцию морем контрабанды». Ни слова о подчинении эскадры Орлову не было в этом многозначащем документе. Спиридов поверил и согласился.
17 июля 1769 г. Екатерина посетила корабли, стоявшие на кронштадтском рейде, вручила адмиралу орден, приказала выдать всем назначенным в экспедицию четырехмесячное жалованье «не в зачет» и потребовала немедленного выхода эскадры в плавание.
Делать было нечего, вечером следующего дня эскадра поставила паруса, вышла из Кронштадта и… стала у Красной Горки, откуда ее можно было увидеть из Кронштадта, но нельзя было увидеть из Петергофа в самую сильную подзорную трубу. И лишь 26 июля эскадра Спиридова по-настоящему ушла в плавание.
Это было фактически первое плавание русской эскадры в открытое море и океан. До этого русский флот действовал лишь у балтийских берегов. Исключение представляли только переходы кораблей и фрегатов, построенных в Архангельске, в Кронштадт вокруг Скандинавии.
Многочисленные поломки судов и болезни команды задерживали продвижение эскадр. Лишь 18 ноября Спиридов на «Св. Евстафии» прибыл в порт Магон на Менорке (Балеарские острова). А 23 ноября в порт Магон на английской бригантине прибыл младший из братьев Орловых — Федор. Братья Алексей и Федор Орловы еще в начале войны приехали в Италию «на лечение». Федор вручил Спиридову новый рескрипт императрицы, согласно которому эскадра и адмирал были подчинены графу Алексею Орлову.
К середине декабря в порту Магон собралось семь русских судов — корабли «Св. Евстафий», «Три Иерарха», «Три Святителя», «Св. Иануарий»; фрегат «Надежда Благополучия»; пинки «Сатурн» и «Соломбала». 4 февраля 1770 г. эскадра Спиридова прибыла на Мальту.
Алексей Орлов решил высадить первый десант в греческом порту Витулло (он же в разных документах — Витило или Витула) на полуострове Майна. Жители этого полуострова (майноты) существовали главным образом грабежом и разбоем и никогда не признавали над собой власти турок.
18 февраля 1770 г. в Витулло с Мальты прибыла эскадра Спиридова, в составе которой были корабли «Св. Евстафий», «Св. Иануарий», «Три Святителя», пинк «Соломбала» и пакетбот «Летучий». В Витулло уже стояло купеческое судно под венецианским флагом, капитан которого был из славян. Граф Орлов нанял его в русскую службу и отправил в Витулло в ожидании прибытия флота. На судне было 20 пушек, и оно салютовало адмиральскому флагу по приходе его. Адмирал произвел капитана этого судна по имени Палекутин в лейтенанты, а судно, названное «Святым Николаем», на другой день подняло русский флаг.
В трюмах каждого русского корабля находилось по одной разобранной малой галере (в некоторых документах они назывались полугалерами). 19 февраля части галер были свезены с кораблей на берег, а уже 23 февраля все три галеры были собраны, оконопачены и спущены в воду. Галера корабля «Св. Евстафий» названа «Касатка», и командиром ее назначен Кумман. Галера корабля «Св. Иануарий» названа «Ласточкой», и командиром ее назначен шкипер этого корабля Лукавич. Галера корабля «Три Святителя» названа «Жаворонком», а командиром назначен Николетти. На каждую галеру дано по 20 человек команды.
25 февраля прибыла греческая полакра под названием «Генрик-Каррон» под командой Александра Алексиано. Она была нанята в нашу службу и в тот же день подняла русский флаг. На ней было установлено 12 пушек.
Во время пребывания флота в порту Витулло несколько больших партий греков под командой русских офицеров были отправлены в разные части Мореи, чтобы овладеть городами и главнейшими укреплениями.