В грудні 1796 року указом імператора Павла І створена нова Новоросійська губернія, до якої увійшла більша частина ліквідованого Катеринославського намісництва. Адміністративним центром був Катеринослав (який протягом 1797—1802 років мав назву Новоросійськ). Новостворена губернія займала територію від Дністра до Дону з Кримом і колишнім Запорожжям, яке стало ядром цієї адміністративної одиниці.

Губернія складалася з 12 повітів:

Катеринославський повіт,
Бахмутський повіт,
Єлизаветградський повіт,
Маріупольський повіт,
Новомосковський повіт,
Ольвіопольський повіт (з центром у Вознесенську до переміщення в Ольвіополь),
Павлоградський повіт,
Перекопський повіт,
Ростовський повіт з Землею Війська Чорноморського поміж річками Єя і Кубань — повітове місто Таганріг,
Сімферопольський повіт,
Тираспольський повіт.
Херсонський повіт.



У 1802 Новоросійську губернію під час чергової реформи було поділено на Миколаївську (з 1803 — Херсонську), Катеринославську й Таврійську губернії.