Вознесенская губерния была открыта 13 июня 4795 г. К построению губернского города Вознесенска в окрестностях местечка Соколов при впадении р. Мертвых Вод в р. Буг приступили лишь в конце 1795 г. В том же году уездный г. Александрию было предписано перенести в местечко Крылов «с наименованием последнего – городом Александрией».

1795 г. был кульминационной точкой в росте территории Новороссии, когда в ее состав вошли значительные пространства Малороссии, Правобережной Украины и Слобожанщины. По существу, весь период с 20‑х по середину 90‑х гг. XVIII в. характеризовался непрерывным ростом земельных просторов Новороссии. Однако Малороссия и Слободская Украина к 20‑м годам XVIII в. имели свои достаточно четко исторически сложившиеся рубежи. Искусственное включение каких-то частей этих районов в состав Новороссии не означало, что они сделались новороссийскими. Плотность, состав населения, его географическое размещение в Новороссии были совсем иными, чем в Малороссии или Слобожанщине, а тем более в Правобережной Украине.

С 1796 г. начинается сравнительно кратковременный, но радикальный по своим результатам период, когда Новороссия лишилась не только приобретенных ею временно частей Малороссии и Слобожанщины, но и территорий, которые органически могли считаться частью этого района (большие части Бахмутского и Донецкого уездов, Константиноградский уезд и т.д.).

30 ноября 1796 г. был опубликован указ о восстановлении в Малороссии прежнего правления и судопроизводства. Указ предписывал: из трех губерний образовать одну с губернским городом Черниговом и причислить «отделенные к Новороссийской, что потом названа Екатеринославской, губернии Полтавский бывший полк, також и бывшего Миргородского полка город Кременчуг с прочими местечками и селениями, а равномерно и уезды, после того к Екатеринославской же губернии отделенные». Это означало, что все малороссийские территории, включенные в состав Новороссии в 1764—1795 гг., подлежали возврату обратно.

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

По штату от 31 декабря 1796 г. Новороссийская губерния делилась на 12 уездов. Однако лишь в августе 1797 г. был опубликован указ, подробно определивший границы Новороссийской губернии. По этому указу предписывалось отделить от бывшей Екатеринославской губернии:

К Малороссии уезды: Градижский, Миргородский, Полтавский, Хорольский, часть Алексопольского (с г. Алексополем), часть Константиноградского (с г. Константиноградом).

К Слободско-Украинской губернии часть Константиноградского и часть Славянского уездов с г. Славянском.

К Воронежской – части уездов Бахмутского, Донецкого и Славянского, «так как по делам значится, что оные места подведомственны прежде были сей губернии».

В Киевскую и Подольскую губернии земли, приписанные к бывшей Вознесенской губернии из приобретенных по разделам Польши земель, а именно: к Киевской губернии – Екатеринопольский, Уманьский, Черкасский и Чигиринский уезды; к Подольской – Ольгопольский уезд и части Богопольского, Еленского и Тираспольского уездов.

Оставшаяся часть Новороссии разделялась на следующие 12 уездов: Екатеринославский, Бахмутский, Елисаветградский, Мариупольский, Новомосковский, Ольвиопольский (с присутственными местами в г. Вознесенске до перемещения их в Ольвиополь), Павлоградский, Перекопский, Ростовский с Землей Войска Черноморского (присутственные места в г. Таганроге), Симферопольский, Тираспольский и Херсонский.

Материалы V ревизии показывают, что новое административное деление было введено в действие лишь со второй половины 1797 г. В 1796 г. Новороссия еще разделяется на Екатеринославскую и Вознесенскую губернии с их уездами. В сентябре 1797 г. вновь созданная Новороссийская губерния подразделяется уже на 12 уездов (Екатеринославский, Новомосковский, Павлоградский, Бахмутский, Ростовский, Мариупольский, Елисаветградский, Ольвиопольский, Херсонский, Тираспольский, Перекопский и Симферопольский).

После этого границы Новороссии несколько лет (1798—1801 гг.) не изменялись. В эти годы происходили лишь отдельные незначительные административные преобразования и переименования. По указу от 26 сентября 1797 г. слобода Балта была передана в состав Подольской губернии и присоединена к г. Еленску «с переименованием оного в Балту», 22 декабря 1797 г. был опубликован указ, по которому губернский город Новороссийской губернии Екатеринослав был переименован в Новороссийск. 24 сентября 1800 г. г. Григориополь Тираспольского уезда был переименован в г. Черный, однако уже 30 января 1802 г. было восстановлено его прежнее название.

В 1802 г. начинается новая радикальная перекройка административной карты Новороссии. Указ 8 октября 1802 г. предписывал:

Разделить Новороссийскую губернию на три губернии: Николаевскую, Екатеринославскую и Таврическую.

Николаевскую губернию (главный город Николаев) составить из четырех уездов: Елисаветградского, Ольвиопольского, Тираспольского и Херсонского.

Екатеринославскую губернию (главный город Екатеринослав) составить из пяти уездов: Екатеринославского (Новороссийского), Бахмутского, Новомосковского, Павлоградского, Ростовского и части Мариупольского.

Таврическую губернию (губернский город Симферополь) (Акмечеть) составить из семи уездов: Симферопольского (Акмечетьского), Днепровского, Евпаторийского (Козловского), Мелитопольского, Перекопского (с отделением к нему части Мариупольского по границе прежней Таврической области), Тьмутараканского (бывшего Фанагорийского) и Феодосийского (Кефийского).

Таким образом, указ этот в урезанном виде воспроизводил деление первой половины 90‑х гг. XVIII в. Таврическая губерния вообще восстановила свои прежние границы. Екатеринославская губерния получила то, что осталось от нее в границах 1795 г., кроме частей, отошедших к Малороссии и Слобожанщине. Исключение представляла территория упраздненного Александрийского уезда, включенная в состав Херсонской губернии.

Херсонская губерния в своих границах примерно соответствовала новороссийской части бывшей Вознесенской губернии с исключением г. Балты и присоединением земель Александрийского уезда.

Материалы V ревизии показывают, что в своем новом составе указанные губернии были сформированы лишь к началу 1804 г. На начало и середину 1803 г. в окладных книгах приводятся данные о народонаселении в границах предшествующего периода. И лишь в окладной книге 1804 г. помещены сведения по уездам в новых губернских границах.

В 1803 г. последовало дальнейшее сокращение территории, принадлежащей Новороссии, даже по сравнению с границами 1797—1802 гг. По указу от 27 марта 1803 г. к Полтавской губернии было присоединено все пространство между реками Берестового и Орелью, «дабы тем восстановить древние пределы Малороссии». На основании этого указа от Новомосковского уезда к Константиноградскому уезду Полтавской губернии отошла значительная территория бывшей Екатерининской провинции (Украинской линии) и граница между Екатеринославской и Полтавской губерниями стала пролегать по р. Орели. С 1803 г. можно уже говорить, что вся Екатерининская провинция вошла в состав Полтавской и Слободско-Украинской губерний.

15 мая 1803 г. Николаевская губерния была переименована в Херсонскую, а губернское управление переведено из Николаева в Херсон.

Разделение Херсонской губернии на 4 уезда, а Екатеринославской – на 5 уездов просуществовало до 1806 г. Источники показывают, что разделение Екатеринославской губернии на 8 уездов было осуществлено в 1805 г.,