По Кучук-Кайнарджийскому мирному договору с Турцией (1774 г.) Россия получила, наконец, выход к Черному морю, однако, чтобы окончательно утвердиться на его берегах, необходим был флот. Имевшаяся эскадра состояла из небольшого числа кораблей, предназначенных для действий лишь вблизи берега, и не могла противостоять мощному турецкому флоту. Промышленная же база для кораблестроения в российском Причерноморье тогда отсутствовала.
Чтобы усилить черноморскую эскадру, решили перевести сюда несколько фрегатов с Балтики, подняв на них торговые флаги. Торговые, поскольку военным кораблям проход проливами был закрыт. Пример имелся: только что из Средиземного в Черное море удалось перевести 3 разоруженных фрегата и 10 мелких судов из состава бывшей Архипелагской эскадры.
Балтийский флот выделил для перевода на Черное море четыре фрегата. Команды трех из них — «Павла», «Григория» и «Натальи» — наполовину сократили, а сами корабли почти полностью разоружили: на батарейных палубах оставили лишь по 8 пушек из 40; остальные — зарыли в песочный балласт, уложенный на днище. Ставшие ненужными орудийные порты зашили и закрасили. И вообще придали фрегатам вид обычных торговых судов, а трюмы их загрузили различными товарами.
Четвертый фрегат — «Северный Орел» — в качестве эскортного боевого корабля пошел под военным флагом и с полным вооружением. Его командир капитан 2 ранга Козлянинов был назначен командиром отряда. В Ливорно к его кораблям должны были присоединиться еще два — «Св. Павел» и «Констанция», оставшиеся там от Архипелагской эскадры.
Во всех официальных документах для сохранения тайны экспедиция именовалась «торговой». Инструкцией Адмиралтейств-коллегии предписывалось ни в какие порты до Средиземного моря не заходить.
15 июня 1776 г. корабли вышли из Кронштадта и без особых происшествий за два месяца обогнули Европу и достигли Гибралтара. 10 сентября уже в итальянских водах отряд соединился со «Св. Павлом» и «Констанцией»; на них также были сняты пушки, погружены товары и поднят торговый флаг. (В командование «Св. Павлом» вступил капитан-лейтенант Ф. Ф. Ушаков — будущий прославленный адмирал — командующий Черноморским флотом.)
В январе 1777 г. три фрегата уже стояли в Константинополе, а три — у входа в Дарданеллы. Начались переговоры о пропуске судов в Черное море, сами по себе представляющие интересную страничку тайной дипломатии. Поскольку корабли были фактически разоружены и шли с грузом, турки, строго следуя букве договора, должны были их беспрепятственно пропустить. Однако правители «Блистательной Порты» сочли это крайне нежелательным и начали очень искусно затягивать решение вопроса. Тянулось это дело... целый год и кончилось тем, что разрешение так и не было дано.
24 декабря 1777 г. Козлянинов принял решение отправиться в обратный путь. Поскольку корабли требовали ремонта, отряд снова зашел в Ливорно. Интересно отметить, что появление русских кораблей в далеких водах способствовало укреплению дружественных отношений с рядом средиземноморских стран. Так, в Ливорно Козлянинов, оказавшийся неплохим дипломатом, нанес визит находившемуся здесь марокканскому посланнику (полномочному министру) и передал ему намерение Екатерины II «пребывать во всегдашнем согласии с народами, не имеющими злых намерений нарушить спокойствие ее подданных». В ответ посланник заявил, что его повелитель дал приказание открыть все гавани его владений для русских судов. В доказательство своей дружбы Козлянинов выделил два фрегата для доставки посланника и его свиты в Танжер.
Произведя ремонт и переждав зимние шторма, 11 марта 1779 г. отряд вышел из Ливорно и 14 мая благополучно прибыл в Кронштадт, завершив почти трехлетнее плавание.
Несмотря на то, что прямая цель экспедиции достигнута не была, она сыграла положительную роль. И не только тем, что содействовала росту авторитета России как морской державы. Учтя ее результаты, русское правительство приняло решение строить флот на месте. Уже в 1778 г. в 30 км от устья Днепра был основан город Херсон — первый кораблестроительный центр на берегах Черного моря. Вскоре здесь был спущен на воду первый линейный корабль Черноморского флота «Слава Екатерины».