В 1775 г. генерал-губернатором Новороссийского края был назначен фаворит Екатерины II Григорий Александрович Потемкин, деятель талантливый, энергичный и облеченный огромными полномочиями. Новороссийская губерния разрасталась. К Малороссии она отношения уже не имела. В нее включались земли, лежавшие за пределами исторической Украины, которые присоединялись Россией в ходе войн с турками. После заключения Кючюк-Кайнарджийского мира в состав Новороссии вошли новые приобретения: низовья Днепра и территории до Буга, а также территории ликвидированной Запорожской Сечи. Центром губернии сперва был Кременчуг. В 1776 г. Потемкин заложил новую губернскую столицу – Екатеринослав (Днепропетровск, а ныне просто Днепр). А потом перенес административный центр в другой новый город, Херсон. Поближе к морю. Здесь началось строительство Черноморского флота. Население в Новороссии стало смешанным: сюда перебирались малороссы (особенно с польского Правобережья), оседали отставные русские солдаты, офицеры получали землю и переводили сюда крепостных из русских имений. Из турецких владений переселелись молдаване, греки, болгары, сербы, арнауты (албанцы). В Приазовье была образована другая губерния, Азовская. Она также была подчинена Потемкину, как и Астраханская.
А Малороссию включили в Киевское генерал-губернаторство. Полковая структура управления была ликвидирована, заменена обычным в России административным делением уездов и волостей. Не стало и малороссийских казачьих полков. Их окончательно упразднили, на их базе создавались части регулярной кавалерии. Это позволило заменить развалившиеся полки полноценными боевыми формированиями. Но Потемкин был не только прекрасным администратором, но и опытным военным. Он видел, что со многими функциями казаков регулярные войска не справляются. Например, Россия после войны вышла на Кубань и столкнулась с непрестанными набегами горцев. Суворов строил по новым границам посты и крепости и возмущался – его превосходных солдат, «чудо-богатырей» горцы попросту «расхищали». На Кавказскую линию стали переселять волжских казаков, посменно высылали дежурить полки донских казаков.
Они оказывались незаменимыми разведчиками и на турецкой, татарской границах. Обстановка в Крыму долгое время балансировала туда-сюда. По условиям мира ханство стало «независимым». Но теперь оно оказалось зажато между владениями Российской и Османской империй, и обе боролись за то, чтобы перетянуть его под свое влияние. Потемкин возвел на ханский престол своего ставленника Шагин-Гирея. Но крымские ханцы были многоженцами, у Шагина было много братьев. Турки засылали то одного, то другого из них, организовывали заговоры. В Крыму то и дело вспыхивали восстания, мятежные татары убивали сторонников Шагин-Гирея, заодно резали и христиан, попавшихся под руку, и возводили на престол новых ханов. Шагин убегал к русским, приходилось раз за разом вводить в Крым войска и с боями возвращать его в Бахчисарай.
А запорожцы издавна изучили все пути-дорожки на полуостров. В ходе этих свистоплясок Потемкин начал создавать команды из бывших запорожцев. Он обратил внимание и на Бугское казачье войско. Его в свое время формировали из правобережных украинских казаков, ушедших к русским из владений Речи Посполитой. Во время войны к бугским казакам добавли подразделения некрасовцев, перешедших на сторону России, добровольческие «арнаутские» команды из молдаван, румын, болгар, сербов, греков. Всего казаков набралось 1,5 тыс., из них сформировали Бугский полк. Ему были выделены земли в междуречье Ингула, Еланца и Мертвовода. Потемкин переселил сюда более 3 тыс. крестьян, покупая их у помещиков, – по его расчетам, содержание 1 боевого казака должны были обеспечивать 4 крестьянина.
Крымские дергания туда-сюда императрице надоели. После очередного мятежа и свержения Шагин-Гирею указали, что таким играм пора положить конец, и в 1783 г. он окончательно отдал Крым в подданство России – его тоже включили в Новороссийскую губернию. В 1787 г. Екатерина предприняла путешествия на юг, Потемкин показывал ей новые города, недавно заселенные земли. Во время этого визита Григорий Александрович представил государыне и делегацию запорожцев, она ходатайствовала о создании «Коша Верных Казаков» – или «Войска Верных Казаков». Екатерина согласилась.