В 1776 году Алексей Наумович Сенявин был уволен в годовой отпуск, а вместо него главным командиром Азовской флотилии был назначен Федот Алексеевич Клокачев, человек энергичный и предприимчивый. Флот Российский, вышедший из азовского мелководья, примеривал новое название — Черноморский. Днепр, Десна и исходный пункт первых русских морских послемонгольских экспедиций Брянск — стали новыми центрами русского судостроения. 18 февраля 1777 года контр-адмиралу Софроку Борисовичу Шубину был отдан приказ осмотреть днепровские пороги, подготовить и провезти вдоль Днепра строительный лес.

В том же году, когда был подписан мир, Екатерина издала указ для Адмиралтейств-коллегии, обязывающий ее на Днепровском лимане, неподалеку от урочища, называемого Глубокая Пристань, близкого к Александровскому шанцу, построенному в войну, «избрать удобное место для построения гавани, в которой можно было бы поместить не менее 20-ти больших военных судов, устроить все потребное для Адмиралтейства... сделать не менее 20-ти или по крайней мере 15-ти эллингов, так чтобы они были вместе один подле другого, дабы все Адмиралтейство и будущие строения можно было обнести укреплениями». Тогда же и был утвержден здесь по причине отдаленности Адмиралтейской коллегии специальный член коллегии для снабжения повелениями и наставлениями.

В 1778 году по повелению Потемкина в 14 верстах от впадения Ингульца в Днепр окончательно было определено место будущего корабельного города. 18 июня там и был заложен по высочайшему указу город и верфи. После смерти Шубина главным руководителем работ был назначен генерал-цейхмейстер Иван Абрамович Ганнибал. Город наименовали — Херсон (следуя тогдашней моде, названия выводили из древней греческой истории и мифологии). Потемкин определил ему роль столицы Таврии (так пышно обозначили этот южный не заселенный еще край). Город стал центром управления Черноморским, Азовским и Каспийским флотами. В Херсоне было учреждено Черноморское адмиралтейское правление. Здесь же были заложены корабельные верфи для постройки гребных и парусных судов. Русский флот на Черном море стал ориентироваться на эту свою новую базу и столицу.

24 ноября 1783 года вместо умершего вице-адмирала Клокачева главным командиром Черноморского флота был назначен контр-адмирал Яков Филиппович Сухотин. В инструкциях Потемкина ему было предписано руководствоваться прежними наказами и обратить главное внимание:

«1) на более поспешную достройку заложенных 6 кораблей и доделку адмиралтейского строения; 2) на заготовку лесов и постройку для Черноморского флота 8-ми новых 50-пушечных фрегатов; 3) на принятие всяких предосторожностей от появляющихся повальных болезней».

А болезни вдруг превратились в главного врага на этих землях. В это время и получил свое назначение на юг, в Черноморский флот, с назначением командиром строящегося в Херсоне корабля № 4 Федор Ушаков. Ему предстояло принять участие в великой эпопее воссоздания Черноморского флота. Здесь, на Черном море, одержит он свои блестящие победы, здесь столкнется с хитростью и коварством, здесь будет надеяться на высокое покровительство и приобретет признание простых моряков, всех тех, кто пришел осваивать море и его берега.

Не ласковым, теплым, здоровым представало Черное море, а диким, буйным, заросшим по берегам колючим кустарником, с тучами малярийных комаров, оседлавших лиманы и озера. Лихоманка трепала первых поселенцев беспощадно, скоро портилась пища, не хватало чистой питьевой воды. Предстояла гигантская созидательная работа по обустройству и возрождению к жизни обширных земель, по созданию Черноморского флота! Это был великий подвиг нашего народа, равный освоению Сибири, выходу на берега Балтики и Тихого океана. Сколько книг, фильмов, песен, посвященных освоению Дикого Запада, создали американцы? Наша эпопея освоения «Дикого Юга» была не менее героична, захватывающа и впечатляюща, однако как великая эпопея в сознании наших людей не закрепилась.

Русские и украинцы стали основным населением полого края, основным, но не единственным. Быстро осели в его новых городах и поселениях греки и армяне, умевшие бойко и прибыльно торговать. Из Молдавии бежали крестьяне и ремесленники, из подневольных и приграничных областей Сербии пробрались кружным путем через Австрию и Польшу югославяне, из нестерпимого османского ада вырывались болгары и черногорцы, словенцы и боснийцы. На русскую военную службу определялись албанцы-арнауты.

Щедрым жестом пригласила на тучные причерноморские земли немцев, чехов, австрийцев Екатерина. Пользуясь близостью территории, постоянно перемещались из Польши в Новороссию поляки, белорусы, евреи. Словом, утверждался особый тип поселенца — человека из разных национальностей, энергичного, предприимчивого, небоязливого, человека, много умеющего. Но была и разница — иностранцы были в основном люди свободные, то есть незакрепощенные, а русские, украинцы, переселенцы из Белоруссии нередко принадлежали помещикам, имевшим на них «дозволенное богом и государством право». Вот эти-то обделенные и не обделенные судьбой люди возводили, строили, поднимали российский Черноморский флот. Ему еще предстояло расписаться победами в книге истории, но он сразу стал реальностью, утверждающей новое состояние на Черном море. В его состав входили Донская (Азовская) и Дунайская флотилии и основная его часть, расположившаяся в Крыму и устье Буга. Русский флот появился тут не случайно, проявились «морские гены» предков, дождались они своего часа. Весельники Святослава, умные ходоки из «варяг в греки» до самого Константинополя, княжеские галеры оставили после Киевской Руси глубокий след в народном сознании. Морскую традицию здесь, у Черного моря, сберегли и продолжили донские и запорожские казаки, ходившие на своих «чайках» к Синопу, Трапезунду и Истамбулу. И вот Черноморский флот воссоздавался и создавался вновь.

Не так это было просто — создать флот в безлесных и степных районах, без кадров рабочих, без выработанного веками умения корабельных мастеров, без устойчивого желания всей нации плавать в далекие края. Ведь до моря от центральных районов страны было больше тысячи, двух, а то и пяти тысяч километров, где уж тут свобода в выборе моряков, как говорят ныне, плавсостава. Но тяготение державы, торговых людей, Петровых последователей, вроде бы вполне сухопутных казаков к морским просторам было не случайно. Были тут и объективная необходимость, и жажда новых открытий, и любопытство, и авантюризм, и державные стремления утвердиться прочно на берегах, и восстанавливаемая историческая справедливость. Быстро возрождалась тогда вековечная морская выучка. Моряк и плотник, солдат и строитель, торговец и предприниматель, помещик и купец, архитектор и священник, инженер и офицер пришли на этот полуденный берег империи. Одни искали здесь счастливой доли, другие хотели получить новые земли и людей, одни давали выход своей творческой натуре, другие стремились накопить капитал, одни не верили ни во что, другие истово искали тут подтверждения первоапостольских знаков, одни искали свободу, другие заковывали ее.

Во вновь возводимые дворцы, крепостные бастионы, солдатские казармы, в сырые землянки горожан вползла страшная беда. На просторах Южной России вспыхнула чума. Большего бедствия в XVIII веке не знали. (Да и в предыдущие века тоже.) Ни войны, ни междоусобицы, ни зверства феодалов и деспотов всех мастей не уносили столько жизней, как эта зловещая болезнь.

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