В ходе организации вновь учреждаемого Саратовского наместничества И.В. Якоби по приказу Потемкина подготовил ему 12 ноября 1780 г. для рассмотрения два списка чиновников, желающих вступить в штат (в одном те, которые уже находятся на службе в губернии, в другом — претенденты из отставных или других губерний). Отличительной чертой местного управления Саратовской губернии было введение в штат представителей иностранных колонистов. Кроме того, учитывая, что в это время Саратовская губерния являлась основным источником соли для всего государства, Якоби предлагал учредить особый департамент при казенной палате.
По присланному от Потемкина расписанию наместничество делилось на 10 уездов. Колонисты пока оставались в ведомстве опекунской конторы, а земли распределялись по уездам с тем, чтобы по окончании устройства поселений на «линии» объединить их в одну округу. Торжественное открытие Саратовского наместничества состоялось 3 февраля 1781 г. с принесением присяги дворянством и купечеством, о чем на следующий день И.В. Якоби рапортовал Потемкину, а тот доложил императрице.
При вступлении в дела, относящиеся к организации Новороссийской и Азовской губерний, Потемкин потребовал у подчиненных губернаторов Муромцева и Черткова, находящихся на местах, полные статистические сведения о состоянии губерний и свои предложения по устройству границ, строительству крепостей и созданию должных условий для заселения и экономического развития земель. Уже 29 июля 1775 г. губернатор Азовской губернии Василий Чертков рапортовал, что «повеленное описание, план и прочее до сей губернии относящиеся сведения доставить он неумедлит». Здесь же он сообщал о препятствиях в строительстве «новой линии» (Днепровской) и писал, что «если построение сей линии да и других крепостей в Новороссийской губернии не будет прямо зависеть от распоряжений вашего высокографского сиятельства, как главного повелителя обеих губерний, то время… будет проходить больше в отвращении различных в работах препятствий и во многих, да иногда и излишних, неминуемых переписках с разными местами…».
9 сентября того же года Потемкин доложил Екатерине, что поручил генералу-поручику П.А. Текели и губернаторам В. Черткову и Муромцеву «разсмотреть границы того края и положить число нужное крепостей для обороны пределов и в преграждение могущих быть от тамошних соседей покушений, соображая укрепления оных с образом войны и вооружения окрестных тех народов». 18 сентября Потемкин писал о поручении, данном своим подчиненным, членам Сената, особо указывая на то, что они должны были, «войдя во все наиподробнейшия тех мест обстоятельства и сообразив чувствуемыя жителями изнеможении, с тою пользою, каковая по пограничности оных ожидаема быть должна» представить «общее свое мнение» о районировании земель и устройстве укрепленных мест. Согласуясь с мнением своих подчиненных, Потемкин предложил императрице построить одну крепость на стечении рек Буга и Днепра, а вторую — на Никитинском перевозе. Ее резолюция: «наименовать первую Херсон, а другую — Словенск». Посылая рапорт в Сенат, Потемкин приложил описание границ Новороссийской и Азовской губерний.
В развитие указа Екатерины II от 8 марта 1776 г. об укреплении границ губерний от возможных нарушений мира со стороны Турции Потемкин предлагал: во-первых, определить губернское правление в крепости Словенске, положение которой «столь полезно, что служит она не только к отвращению всяких набегов, но и к достаточному сопротивлению, а особливо противу легкако и не имеющаго всех нужных снарядов неприятеля…»; кроме этого, «окруженное ретрашементом предместье может служить к довольному помещению не только мещан, но и к безопасному убежищу в случае нужды сельских жителей… Сия крепость прикрывать будет тамошней перевоз чрез Днепр и впадающую в оной речку Подпольную».
Во-вторых, по мнению Потемкина, основанному на донесениях губернаторов, выбранное место для постройки Херсона с гаванью «за мелкостию там воды» не подходит. Он задумывает устроить крепость при Глубокой пристани, «где в разных кварталах как морские, так и сухопутные силы со всеми их принадлежностями, в разных отделениях расположась, удобно защищены будут, где и главной для оных крепостей арсенал полагается».
В-третьих, Потемкин полагает необходимым «для занятия пространства между Словенским и Херсоном и ради прикрытия нужнаго там чрез Днепр перевоза» устроить крепость под названием Новогригорьевская.
В-четвертых и в-пятых, для удобной связи между крепостями Херсон и Екатеринск и «ради распространяющихся по реке Бугу с довольным успехом ретраншированных селений вербованных казак арнаут» необходимо устроить две крепости — Новоалександровскую и Новопавловскую, названные, по всей вероятности, в честь сына и внука императрицы.
Последним пунктом Потемкин представляет постройку крепости Екатерининской, «под которую занимается самое наивыгоднейшее пред протчими в той околичности место, где ныне состоит Екатерининский шанец с прибавлением к нынешним его линеям некоторых нужных укреплений потому, что в пункте сем смыкаются польския и турецкия границы».
Потемкин планирует построить указанные крепости за пять лет и посылает реестры о необходимых суммах и количестве мастеровых людей для производства работ, расписывая все погодно. Главным инженером при крепостях Новороссийской губернии и Днепровской линии генерал-губернатор считает необходимым назначить находящегося при Днепровской линии в должности инженер-подполковника Шалыгина, показавшего себя опытным специалистом.
Одно из первых предложений по изысканию средств на обустройство губерний было сделано в апреле 1776 г. Потемкин предлагал денежные средства, оставшиеся после уничтожения Запорожской Сечи (120 000 р.), использовать на составление городского капитала, из него жители губерний по установленным правилам могли получать на распространение «домостроительства и торговли в разсуждении заселяемых ими степных почти мест».
Осуществление планов Потемкина продвигалось не без трудностей. Так, например, 27 августа 1776 г. он сделал выговор генералу А.И. Медеру, которому в 1775 г. было поручено строение крепостей. Как пишет в ордере князь, вместо успехов «не могу еще поныне получить от вас и проектов тем крепостям с сметами… Итак, подтверждая в последний раз, ожидаю скорейшаго отправления от вас проектов и смет…».
Вскоре после образования Новороссийской и Азовской губерний было разработано несколько проектов по их устройству. Они были составлены губернатором Азовской губернии В.А. Чертковым (1726–1793) по поручению Г.А. Потемкина и на основании его рекомендаций. Василий Алексеевич Чертков принадлежал к древнему дворянскому роду. В 1748 г. он поступил на государственную службу и в 1764 г. был произведен в бригадиры с назначением обер-комендантом крепости Св. Елизаветы, построенной по ходатайству сербского генерал-майора Хорвата для защиты сербских переселенцев. В 1771 г. он был пожалован в генерал-майоры и с 1776 по 1782 г. исполнял должность Азовского губернатора, был командиром Днепровской линии, а с 1777 г. — генерал-поручиком поселенных в Азовской губернии регулярных и иррегулярных полков и шефом Пики-нерского Луганского полка. Надо заметить, что В.А. Чертков, кроме хорошего знания обстановки в губернии, обладал и литературным талантом. Его перу принадлежит комедия «Кофейный дом» (1770) и «Обряд при Высочайшем шествии Екатерины II через Харьковское наместничество» (1787).
Проекты, составленные Чертковым, оказали большую помощь Потемкину, показав мнение человека, хорошо знакомого с местными проблемами. Начиная государственную деятельность, Потемкин еще не имел сформировавшейся собственной канцелярии, и Чертков стал одним из первых его сподвижников, творчески воплощая распоряжения и предлагая нововведения. Дальнейшая карьера губернатора Азовской губернии сложилась удачно. В 1782 г. Василий Алексеевич был назначен генерал-губернатором Воронежского и Харьковского наместничеств и в 1787 г., в день торжественного посещения Харькова императрицей Екатериной II, пожалован брильянтовым перстнем и 6000 руб. на подъем во вновь вверенную ему Саратовскую губернию.