В 1777 г. князь отправился для осмотра вверенного ему наместничества: губерний Новороссийской, Астраханской и Саратовской, то есть всей тогдашней Южной Россией от Черного до Каспийского моря. В это время в уме Потемкина созрела мысль, за которую он взялся со всей пылкостью и решимостью своего характера; это проект изгнания турок из Европы и восстановление Византийской империи с царями русской династии. Новороссийский край должен был служить 1-й ступенью огромного предприятия. Голую степь предстояло заселить, обустроить, вооружить.
В 1779 г. был заложен Херсон и построены войсковые казармы в виде мазанок. В 1780 г. князь приехал в Кременчуг. Императрица вверила ему полномочную власть и миллионы рублей. На его клич в безлюдный край хлынули поселенцы со всех сторон: греки из Мореи и с архипелага, армяне из Крыма и Закавказья, итальянцы и немцы, калмыки из Уральских степей; запорожцы, убежавшие за границу, теперь начали снова возвращаться на старое пепелище; раскольники тоже спешили воспользоваться особыми местами, выхлопотанными для них светлейшим в Новороссии. Селения и города вырастали как грибы.
Между тем пало ханство Крымское: Потемкин заставил Шагин-гирея добровольно отречься от престола, и манифест Екатерины известил Европу, что полуостров Крымский, остров Тамань и Кубанская страна присоединяются к России. В то же время царь Грузинский Ираклий присягнул на верность Екатерине и ее наследникам. Новоприобретенная Таврическая область, со своими солончаками, благодатным южным берегом, великолепными гаванями, поступила в управление Потемкина.
Он опоясал крепостями Черное море и открыл его берега для торговли. Порты херсонский, феодосийский и севастопольский получили одинаковые привилегии с Петербургом и Архангельском. Для облегчения сообщений с внутренней Россией были пробиты Днепровские пороги. В самом крае начали процветать промышленность, хозяйство, даже просвещение, так как князь везде учреждал училища уездные и земледельческие, а в Екатеринославе намеревался открыть даже университет. Екатерина продолжала осыпать милостями ревностного исполнителя своих предначертаний.
В 1782 г. Потемкин был поставлен третьим в списке удостоенных кавалеров вновь учрежденного ордена Св. Владимира (после наследника престола и князя Вяземского). В начале 1784 г. он был пожалован президентом Военной коллегии с чином генерал-фельдмаршала. Это новое повышение, подчинившее все военные силы России главному управлению Потемкина, князь ознаменовал многими благоразумными распоряжениями и полезными переменами. В 1786 г. был издан устав, которым бюджет армии определялся со строгой точностью во всех подробностях. Для искоренения лихоимства Потемкин ввел частые и строгие инспекторские смотры, и сам неустанно следил, чтобы солдат был сыт, хорошо одет и по возможности удобно помещен на квартире; изыскивая средства к улучшению материальной обстановки нижних чинов, поднятию их нравственного духа и облегчению во всех отношениях; побои и жестокие наказания преследовались. В заботе о здоровье солдата князь обратил внимание на состояние госпиталей. Кроме того, он начал хлопотать о возвращении запорожских казаков на службу Русскому государству, что ему и удалось осуществить в начавшуюся с турками войну 1787–1791 гг., причем запорожцам предоставили право установить свой войсковой кош на прежнем основании, с выбором войскового старшины, в том же порядке, как это и прежде существовало в войске Запорожском.
Получив такое разрешение, запорожцы в 1787 г., собравшиеся из России и из-за границы, сначала сформировали волонтерскую команду под предводительством запорожского старшины Сидора Белого, а затем, в следующем году, основали войсковой кош на берегу Бугского лимана в урочище Васильково и произвели выборы атамана. Первым кошевым атаманом был избран Сидор Белой. После сего волонтерская команда была преобразована в войско верных казаков, получившее вскорости название Черноморского.
Это войско поступило в действующую армию под главное начальство самого фельдмаршала князя Потемкина.
Сформировав таким образом казачье войско из запорожцев, Потемкин начал совершенствовать свое «войско верных казаков» и заботиться о них, как добрый отец о своих детях. Он дал этому войску флотилию, артиллерию, вооружил и обмундировал казаков, продовольствовал их и удовлетворял жалованьем.
А так как у этих казаков, при разорении Днепровской сечи, были вытребованы в Петербург войсковые клейноды, то, дабы созданное им войско не оставалось без войсковых отличий, а кошевой атаман без присвоенного ему атаманского знака, Потемкин исходатайствовал им войсковое знамя, булаву для атамана и войсковую печать.
