Мир Кучук-Кайнарджийский означал, что бывшее Русское море возвращало себе свое старое предназначение — быть южным окном Руси в Европу. Однако для полновластного утверждения на нем нужен был сильный флот.
В 1775 году вице-адмирал Алексей Наумович Сенявин осмотрел устья Днепра и Буга, и на основании его донесений 11 декабря 1775 года Адмиралтейств-коллегии было дано повеление рассмотреть вопрос о военном судостроении на Днепре, о сооружении Адмиралтейства, о поиске строительных материалов.
В 1776 году Алексей Наумович Сенявин был уволен в годовой отпуск, а вместо него главным командиром Азовской флотилии был назначен Федот Алексеевич Клокачев, человек энергичный и предприимчивый. Флот Российский, вышедший из азовского мелководья, примеривал новое название — Черноморский. Днепр, Десна и исходный пункт первых русских морских послемонгольских экспедиций Брянск — стали новыми центрами русского судостроения. 18 февраля 1777 года контр-адмиралу Софроку Борисовичу Шубину был отдан приказ осмотреть днепровские пороги, подготовить и провезти вдоль Днепра строительный лес.
В том же году, когда был подписан мир, Екатерина издала указ для Адмиралтейств-коллегии, обязывающий ее на Днепровском лимане, неподалеку от урочища, называемого Глубокая Пристань, близкого к Александровскому шанцу, построенному в войну, «избрать удобное место для построения гавани, в которой можно было бы поместить не менее 20-ти больших военных судов, устроить все потребное для Адмиралтейства… сделать не менее 20-ти или по крайней мере 15-ти эллингов, так чтобы они были вместе один подле другого, дабы все Адмиралтейство и будущие строения можно было обнести укреплениями». Тогда же и был утвержден здесь по причине отдаленности Адмиралтейской коллегии специальный член коллегии для снабжения повелениями и наставлениями.
В 1778 году по повелению Потемкина в 14 верстах от впадения Ингульца в Днепр окончательно было определено место будущего корабельного города. 18 июня там и был заложен по высочайшему указу город и верфи. После смерти Шубина главным руководителем работ был назначен генерал-цейхмейстер Иван Абрамович Ганнибал. Город наименовали — Херсон (следуя тогдашней моде, названия выводили из древней греческой истории и мифологии). Потемкин определил ему роль столицы Таврии (так пышно обозначили этот южный не заселенный еще край). Город стал центром управления Черноморским, Азовским и Каспийским флотами. В Херсоне было учреждено Черноморское адмиралтейское правление. Здесь же были заложены корабельные верфи для постройки гребных и парусных судов. Русский флот на Черном море стал ориентироваться на эту свою новую базу и столицу.
24 ноября 1783 года вместо умершего вице-адмирала Клокачева главным командиром Черноморского флота был назначен контр-адмирал Яков Филиппович Сухотин. В инструкциях Потемкина ему было предписано руководствоваться прежними наказами и обратить главное внимание:
«1) на более поспешную достройку заложенных 6 кораблей и доделку адмиралтейского строения; 2) на заготовку лесов и постройку для Черноморского флота 8-ми новых 50-пушечных фрегатов; 3) на принятие всяких предосторожностей от появляющихся повальных болезней».
А болезни вдруг превратились в главного врага на этих землях. В это время и получил свое назначение на юг, в Черноморский флот, с назначением командиром строящегося в Херсоне корабля № 4 Федор Ушаков. Ему предстояло принять участие в великой эпопее воссоздания Черноморского флота. Здесь, на Черном море, одержит он свои блестящие победы, здесь столкнется с хитростью и коварством, здесь будет надеяться на высокое покровительство и приобретет признание простых моряков, всех тех, кто пришел осваивать море и его берега.
Не ласковым, теплым, здоровым представало Черное море, а диким, буйным, заросшим по берегам колючим кустарником, с тучами малярийных комаров, оседлавших лиманы и озера. Лихоманка трепала первых поселенцев беспощадно, скоро портилась пища, не хватало чистой питьевой воды. Предстояла гигантская созидательная работа по обустройству и возрождению к жизни обширных земель, по созданию Черноморского флота! Это был великий подвиг нашего народа, равный освоению Сибири, выходу на берега Балтики и Тихого океана. Сколько книг, фильмов, песен, посвященных освоению Дикого Запада, создали американцы? Наша эпопея освоения «Дикого Юга» была не менее героична, захватывающа и впечатляюща, однако как великая эпопея в сознании наших людей не закрепилась.
Русские и украинцы стали основным населением нового края, основным, но не единственным. Быстро осели в его новых городах и поселениях греки и армяне, умевшие бойко и прибыльно торговать. Из Молдавии бежали крестьяне и ремесленники, из подневольных и приграничных областей Сербии пробрались кружным путем через Австрию и Польшу югославяне, из нестерпимого османского ада вырывались болгары и черногорцы, словенцы и боснийцы. На русскую военную службу определялись албанцы-арнауты.