В 1777–1779 гг. по предложению Г.А. Потемкина была создана укрепленная линия от Моздока до земель Войска Донского, состоявшая из крепостей, между которыми располагались редуты, посты и заставы. Именно светлейшему князю предстояло заниматься налаживанием добрососедских отношений между горскими народами и русскими переселенцами, занимавшими земли новой укрепленной линии, организовывать систему управления. В декабре 1779 г. «Малой Кабарды черного народа старшины и все того народа общество» принесли присягу.

В утверждение клятвы кабардинские владельцы «целовали Коран» и прикладывали вместо печатей и подписей «пальцы» за себя и за весь свой народ. Сначала кавказская знать сама занималась решением вопросов управления на своих землях, а русские военные чиновники под управлением Потемкина обеспечивали жизнедеятельность крепостей Моздокской линии, безопасность жителей, улаживали взаимоотношения горских народов с поселенцами и вмешивались в юрисдикцию «владельцев» в случае, когда они не справлялись со спорными вопросами. На Северном Кавказе постепенно складывалась система русской администрации, развивались торговые связи между населением Кавказского наместничества и горскими жителями, которые, с определенными трудностями, включались в политическую и экономическую жизнь Российской империи. Заслуга Потемкина в том, что организовано это было по возможности мирно и взаимовыгодно.

Потемкин стал инициатором переселения на укрепленную линию между Моздоком и Азовом иностранных колонистов, в основном немцев, поселенных в 1760-е гг. около Саратова. 16 сентября 1778 г. генерал-прокурор Сената князь А.А. Вяземский писал ему, что «согласно словесному моему с Вашею светлостию объяснению» он подал соответствующий доклад императрице, и тот был удостоен «высочайшей конфирмации». Для реализации идеи Потемкина в саратовские колонии будет послан нарочный от Канцелярии опекунства иностранцев, он займется отбором колонистов, одновременно будет составлена смета на организацию переселения и строительство новых домов, обзаведение скотом, семенами и «прочим нужным для хлебопашества»; все материалы в обязательном порядке пройдут «апробацию» государева наместника в новых землях. Князь Вяземский также предлагал Потемкину «для лутче же достоверности в сем предприятии от общества желающих к переселению колонистов человек двух или трех свозить и на те места, куда их переселять назначается, дабы они сами доброту земли и все свои выгодности наперед знать могли». Кроме этого, в Сенате была составлена ведомость о «числе душ, объявивших желание к переселению в Кавказское наместничество» по 22 губерниям Российской империи; всего высказало такое желание 39 698 человек (26 229 мужчин и 13 469 женщин).

Осенью 1776 г. губернатор Астраханской губернии И.В. Якоби, а также губернаторы Новороссийской губернии М.В. Муромцев и Азовской — В.А. Чертков получили секретные ордера Потемкина, предписывающие им всячески помогать графу П.А. Румянцеву-Задунайскому, командовавшему всеми войсками «к стороне Крыма» в его требованиях, «касающихся до земских распорядков», что было связано со сложной политической обстановкой на южных рубежах государства.

В целях поощрения лиц, доставляющих информацию о соседних землях, Потемкин весной 1777 г. представил Екатерине II доклад, основанный на рапорте И.В. Якоби, просившего разрешения награждать недорогими часами и тульской работы вещами людей, употребляемых для разных «разведываний».

Заботясь о «народном удовольствии» жителей Астраханской губернии, Потемкин обратился в Сенат за разрешением сложить таможенную пошлину с вывоза, привозимого из Персии, хлеба и красного дерева, называя основную причину, — удаленность и пограничное состояние города Астрахани. Сенат разрешил беспошлинный привоз не только хлеба и красного дерева, но и любого строевого и дровяного леса, что, несомненно, благоприятно сказалось на развитии края.

Следующим шагом Потемкина по управлению Астраханской губернией стала полная смена состава правления, кроме прокурора, о чем он доложил в июне 1776 г. рапортом Сенату. В нем называется причина столь решительных мер: «…известясь из репорта Астраханской губернской канцелярии, — пишет Потемкин, — о запущенных бывшими в оной присутствующими разных годов не решенных интересных челобитчиковых и апелляционных делах… не оставил предписать той канцелярии], чтобы для решения всех запущенных дел присутствующия съезжались каждой день сверх положенного времяни в присутствие после обеда, и о успехах того решения присылали краткие ведомости, сколько когда ими решено будет». Обращаясь в Сенат, Потемкин просит в случае поступления жалоб на замедление в рассмотрении дел «приписать» их предыдущему составу правления, на что Сенат решил считать распоряжения Потемкина основательными. В 1776 г. в Сенате при обсуждении плана города Саратова, составленного предыдущим Астраханским генерал-губернатором П.Н. Кречетниковым после пожара, было определено предоставить осуществление плана на усмотрение Потемкина.

В ходе организации вновь учреждаемого Саратовского наместничества И.В. Якоби по приказу Потемкина подготовил ему 12 ноября 1780 г. для рассмотрения два списка чиновников, желающих вступить в штат (в одном те, которые уже находятся на службе в губернии, в другом — претенденты из отставных или других губерний). Отличительной чертой местного управления Саратовской губернии было введение в штат представителей иностранных колонистов. Кроме того, учитывая, что в это время Саратовская губерния являлась основным источником соли для всего государства, Якоби предлагал учредить особый департамент при казенной палате.

По присланному от Потемкина расписанию наместничество делилось на 10 уездов. Колонисты пока оставались в ведомстве опекунской конторы, а земли распределялись по уездам с тем, чтобы по окончании устройства поселений на «линии» объединить их в одну округу. Торжественное открытие Саратовского наместничества состоялось 3 февраля 1781 г. с принесением присяги дворянством и купечеством, о чем на следующий день И.В. Якоби рапортовал Потемкину, а тот доложил императрице.

При вступлении в дела, относящиеся к организации Новороссийской и Азовской губерний, Потемкин потребовал у подчиненных губернаторов Муромцева и Черткова, находящихся на местах, полные статистические сведения о состоянии губерний и свои предложения по устройству границ, строительству крепостей и созданию должных условий для заселения и экономического развития земель. Уже 29 июля 1775 г. губернатор Азовской губернии Василий Чертков рапортовал, что «повеленное описание, план и прочее до сей губернии относящиеся сведения доставить он неумедлит». Здесь же он сообщал о препятствиях в строительстве «новой линии» (Днепровской) и писал, что «если построение сей линии да и других крепостей в Новороссийской губернии не будет прямо зависеть от распоряжений вашего высокографского сиятельства, как главного повелителя обеих губерний, то время… будет проходить больше в отвращении различных в работах препятствий и во многих, да иногда и излишних, неминуемых переписках с разными местами…».

9 сентября того же года Потемкин доложил Екатерине, что поручил генералу-поручику П.А. Текели и губернаторам В. Черткову и Муромцеву «разсмотреть границы того края и положить число нужное крепостей для обороны пределов и в преграждение могущих быть от тамошних соседей покушений, соображая укрепления оных с образом войны и вооружения окрестных тех народов». 18 сентября Потемкин писал о поручении, данном своим подчиненным, членам Сената, особо указывая на то, что они должны были, «войдя во все наиподробнейшия тех мест обстоятельства и сообразив чувствуемыя жителями изнеможении, с тою пользою, каковая по пограничности оных ожидаема быть должна» представить «общее свое мнение» о районировании земель и устройстве укрепленных мест. Согласуясь с мнением своих подчиненных, Потемкин предложил императрице построить одну крепость на стечении рек Буга и Днепра, а вторую — на Никитинском перевозе. Ее резолюция: «наименовать первую Херсон, а другую — Словенск». Посылая рапорт в Сенат, Потемкин приложил описание границ Новороссийской и Азовской губерний.