Балтийский отряд состоял из 4 фрегатов. 40-пушечного «Северного Орла» и 32-пушечных «Павла», «Григория» и «Натальи». «Павел», «Григорий» и «Наталья» изображали собой купеческие суда. Они шли под коммерческим флагом, имели половинное число команды и только 18 пушек. На них были погружены различные товары – железо, кожи, воск, икра, парусное полотно, лен. «Северному Орлу» было предписано нести военный флаг и осуществлять конвоирование «купцов».
«Григорий» и «Наталья» шли прямо в Константинополь, а «Павел» должен был зайти сначала в Ливорно, где его поджидали еще два фрегата – 26-пушечные «Св. Павел» и «Констанция». Они были куплены русским флотом во время войны. Для укомплектования кораблей на «Павле» дополнительно разместили команду и товары для них.
Но торговля была всего лишь благовидным предлогом для экспедиции. Если бы корабли прошли проливы, то морские силы России на Черном море получили солидную поддержку. Довооружившись фрегаты могли бы стать хорошей основой будущего Черноморского флота. Для этого надлежало предпринять все меры, чтобы слухи о плавании отряда не достигли ушей султана раньше самих кораблей. Поэтому, например, командиры кораблей и старшие офицеры были назначены только из добровольцев. В инструкции, данной Адмиралтейств-коллегией Козлянинову особо подчеркивалось, что он «ни в какие порты без крайней нужды не заходить не имеет». Более того, при входе в Дарданеллы предписывалось «… <пушечные> станки разобрать, заколотить борта, так чтоб оное не мало не имело вида военнаго судна, оставя однако же пушек 6 или 8-м». Помимо основной целы – прорыва в Черное море – Козлянинову указывалось «сколько возможно стараться ему описывать» те берега, острова и порты, где он будет находиться. Эти сведения очень бы пригодились при составлении будущей лоции Средиземного и других морей.
В ночь на 15 июня (ст. ст.) 1776 года отряд тайно снялся с якоря на Кронштадском рейде и отправился в поход. Прошло полгода и «Павел», «Григорий», «Наталья», «Св. Павел», «Констанция» собрались в Константинопольской гавани. Первая часть похода была успешно выполнена. «Северный Орел» как военный корабль не имел права входа в Дарданеллы. Он остался крейсировать у анатолийского берега, описывая его.
Но когда казалось, что желанное Черное море уже близко, экспедицию постигла неудача. Подстрекаемые английским и французским послами турецкие власти и без того подозрительно относившиеся к слишком большим «купцам», наотрез отказались пропустить их. Не помогло делу и личное вмешательство Козлянинова, многочисленные посулы и подарки, раздаваемые им чиновникам. Безуспешно простояв около 9 месяцев, отряд двинулся в обратный путь. Небольшим положительным итогом стала торговля, которую экспедиция вела все это время. Кроме того, вместе с кораблями на Родину отправились несколько бывших русских пленных, освобожденных согласно мирному договору, но не имевших никаких денежных средств, чтобы добраться домой.
В конце января 1778 года корабли экспедиции вновь бросили якорь на рейде Ливорно. Потрепанные зимними штормами фрегаты нуждались в ремонте, который затянулся до конца апреля. За это время Тимофей Гаврилович завязал дружеские отношения с мароккским посланником Маакмет-Бей-Абдет-Маликом, который прибыл в Ливорно из Флоренции после заключения мирного договора. Результатом отношений стал договор об открытии портов Марокко для российских судов. Более того, Козлянинов рискнул предоставить «Павла» и «Констанцию» для отвоза посланника, его канцелярии и бывших пленников в Танжер. Риск оправдался. Воспользовавшись удачным случаем, командиры фрегатов в течение месяца вели опись берегов Танжера и его рейда. Эти сведения в сочетании с договором дали бы возможность русскому флоту иметь хорошую базу на пути в Средиземное море.
30 августа отряд снова соединился, уже в Гибралтаре. Однако дальше идти было опасно. Качество итальянского ремонта оказалось неважным. На «Павле» и «Григории» обнаружили течь, причем на «Григории» ее невозможно было исправить без килевания. Козлянинов не решился идти в осенний океан на неисправных кораблях. «С общего командующих согласия» отряд вернулся в Ливорно, где и простоял до 11 марта 1779 года. И только тогда корабли «пошли… в море для следования к своим портам». Путь до Кронштадта обошелся без значительных происшествий, и 14 мая все фрегаты благополучно достигли родной земли.
И хотя главная цель экспедиции так и не была достигнута, но ценный гидрографический материал, привезенный ею – сведения о подходах к Дарданеллам, Танжеру, Ливорно, описание итальянских, испанских, турецких, греческих берегов и островов – лег в основу создания карт будущего театра военных действий. Да и выручка от продажи товаров была не лишней для государственной казны.