Рождение нового города шло совсем не просто. Потемкину пришлось приложить немало усилий в борьбе с извечными российскими пороками. В одном из писем царице он писал: «Измучился, как собака и не могу добиться толку по адмиралтейству. Все запущено, ничему нет порядочной записи. По прочим работам также неисправно, дороговизна подрядов и неисправность подрядчиков истратили много денег и время… Никто из тех, кои должны были смотреть, не были при своем деле… все были удалены, а в руках все находилось у секретаря у Ганибалова… которого он увез с собой, не оставив здесь ни лесу, ни денег».

Светлейший князь был раздражен тем, что И.А. Ганнибал, руководивший Херсонским адмиралтейством и доложивший в Петербург, что, согласно указу императрицы, к началу 1783 г. будут готовы 7 кораблей, не сумел построить все корабли. «Теперь выходит, что и лесу всего на корабли не выставлено, а из выставленного много гнилого», – писал Потемкин своей тайной супруге. Однако Ганнибал, приехав в столицу, смог убедить Екатерину II в своей исправной службе. Екатерина пишет Потемкину: «Сюда приехал Ганнибал и уверил меня, что крепость совершенно в безопасном положении противу нечаянного нападения, и что корабли отстраиваются, я для славы города Херсона… дала строителю большой крест владимирской. Не сумневаюсь, что в твоих руках и твоим попечением все пойдет как должно…».

«Третьей столицей России» после первопрестольной Москвы и имперского Санкт-Петербурга должен был стать южнороссийский Екатеринослав. Указ о его основании был подписан Екатериной II в 1784 г. Для города была выбрана живописная местность на правом берегу Днепра. Здесь издавна существовали крупные поселения запорожцев, а также крепости Старый Кодак, Каменка, Половица и Новый Кодак. Строительство нового города началось на месте Половицы. Старый и Новый Кодак вошли в состав в качестве форштадтов (пригородов) Екатеринослава..

Фактическое строительство началось только в 1786 г. Датой же основания Екатеринослава считается 1787 г. К началу новой войны между Россией и Турцией удалось построить не слишком много. Сказывалась нехватка денег. Однако были возведены основные здания центральной части города. Первый камень в основание кафедрального Преображенского собора заложила сама императрица. В годы Русско-турецкой войны 1787—1791 гг. по приказанию князя Г.А. Потемкина в Екатеринославе был построен казенный литейный завод, на котором по русским конструкциям переливались трофейные турецкие пушки.

Строительство Черноморского флота проходило в сложных условиях: промышленная база для кораблестроения была очень слабой. Чтобы ускорить пополнение Черноморского флота, в Петербурге решили перевести на юг часть кораблей с Балтики. Небольшая эскадра в составе шести фрегатов вышла из Кронштадта в Черное море. Корабли совершили поход вокруг Европы и дошли до Дарданелл. Однако Турция отказалась пропустить их в Черное море. Целый год продолжались переговоры с Портой, но окончились они безрезультатно. Балтийские корабли возвратились обратно в Кронштадт.

Азов и Таганрог стали базой создания Азовской флотилии.

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

Некоторые итоги освоения Новороссии к 1783 г. можно обозначить, используя данные, полученные В.М. Кабузаном в ходе его исследований:

«В 1776—1782 гг. наблюдались исключительно высокие темпы прироста населения Новороссии. За небольшой период (примерно 7 лет) население края (в границах начала XIX в.) почти удвоилось (возросло на 79,82 %). Главную роль в этом сыграли переселенцы из соседней Левобережной Украины. Приток новоселов из Правобережной Украины и Центрально-Черноземного района России не был велик. Переселения же из-за границы имели важное значение только для отдельных локальных территорий (Александровского, Ростовского и Херсонского уездов). В 70‑е гг. заселялись еще преимущественно северные и центральные районы Новороссии, причем с 1777 г. на первый план выходит частновладельческое переселенческое движение. Царские власти в указанный период не предпринимали эффективных мер к переводу в Новороссию больших групп переселенцев из-за границы и других районов страны. Они раздавали огромные земельные массивы в руки частных владельцев, предоставляя им право самим позаботиться об их заселении. Этим правом широко воспользовались помещики Новороссии. Они всеми правдами и неправдами заманивали на свои земли крестьян из соседней Левобережной и Правобережной Украины…

А.А. Скальковский приводит интересные данные о посевах и урожае хлеба на всей территории Новороссии в 1778—1782 гг. Они показывают, что земледелие еще не получило большого развития на территории края. В 1778 г. здесь было посеяно 115 209, а собрано – 796 четвертей разного хлеба; в 1779 г. посеяно 148 200, собрано – 365 четвертей; в 1780 г. посеяно 125 187, собрано – 236 816 четвертей; в 1781 г. посеяно 195 215, собрано – 241 745 четвертей и в 1782 г. посеяно 146 804, собрано – 677 187 четвертей хлеба.

И тем не менее Северное Причерноморье быстро заселялось и осваивалось, несмотря на огромные трудности, стоящие на пути переселенцев. Крестьянство, спасаясь от крепостнической неволи, в поисках лучшей доли шло сюда, с колоссальными усилиями распахивало целинные земли и превращало Новороссию в обжитой район…».

В целом рост населения Новороссии происходил очень быстро. Если в 1781 г. здесь было учтено 157 526 «мужских душ», то на 1 января 1783 г. этих «душ» было уже 193 451.

Два указа Екатерины II от 22 января 1784 г. определили структуру Екатеринославского наместничества. По этим указам Екатеринославская губерния делилась на 15 уездов: Екатеринославский, Александрийский, Алексопольский, Бахмутский, Донецкий, Елисаветградский, Константиноградский, Кременчугский, Мариупольский, Новомосковский, Ольвиопольский, Павлоградский, Полтавский, Славянский и Херсонский. Было создано несколько новых уездных городов: Александрия – из бывшего Березовского и Бечийского шанцев, Новомосковск – из Екатеринослава I, Екатеринослав II – на месте запорожского селения Половица, Донецк – из войскового села Подгороднего. В Алексопольском уезде не было городов, поэтому уездным центром было сделано местечко Нехвороща, переименованное в город Алексополь. Крепость Белевскую преобразовали в уездный город Константиноград, а город Тор в Славянск. В Бахмутской провинции (Бахмутский уезд и Славяно-Сербия) возникло два уезда: Бахмутский и Донецкий.

На землях Войска Запорожского появились Екатеринославский, Новомосковский, Павлоградский, большая часть Мариупольского и Алексопольского и отдельные части Херсонского и Ольвиопольского уездов.

На землях Полтавского и Миргородского полков, отошедших в 1764 и 1775 гг. к Новороссии, в 1784 г. образовалось два уезда: Полтавский и Кременчугский. Из этих уездов в состав Новороссии вошли Екатеринославский, Александрийский, Елисаветградский, Мариупольский, Новомосковский, Ольвиопольский, Павлоградский, Херсонский уезды, а также большая часть Алексопольского, Бахмутского и Донецкого уездов. Константиноградский, Кременчугский