В развитие указа Екатерины II от 8 марта 1776 г. об укреплении границ губерний от возможных нарушений мира со стороны Турции Потемкин предлагал: во-первых, определить губернское правление в крепости Словенске, положение которой «столь полезно, что служит она не только к отвращению всяких набегов, но и к достаточному сопротивлению, а особливо противу легкако и не имеющаго всех нужных снарядов неприятеля…»; кроме этого, «окруженное ретрашементом предместье может служить к довольному помещению не только мещан, но и к безопасному убежищу в случае нужды сельских жителей… Сия крепость прикрывать будет тамошней перевоз чрез Днепр и впадающую в оной речку Подпольную».

Во-вторых, по мнению Потемкина, основанному на донесениях губернаторов, выбранное место для постройки Херсона с гаванью «за мелкостию там воды» не подходит. Он задумывает устроить крепость при Глубокой пристани, «где в разных кварталах как морские, так и сухопутные силы со всеми их принадлежностями, в разных отделениях расположась, удобно защищены будут, где и главной для оных крепостей арсенал полагается».

В-третьих, Потемкин полагает необходимым «для занятия пространства между Словенским и Херсоном и ради прикрытия нужнаго там чрез Днепр перевоза» устроить крепость под названием Новогригорьевская.

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

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

Потемкин планирует построить указанные крепости за пять лет и посылает реестры о необходимых суммах и количестве мастеровых людей для производства работ, расписывая все погодно. Главным инженером при крепостях Новороссийской губернии и Днепровской линии генерал-губернатор считает необходимым назначить находящегося при Днепровской линии в должности инженер-подполковника Шалыгина, показавшего себя опытным специалистом.

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

Осуществление планов Потемкина продвигалось не без трудностей. Так, например, 27 августа 1776 г. он сделал выговор генералу А.И. Медеру, которому в 1775 г. было поручено строение крепостей. Как пишет в ордере князь, вместо успехов «не могу еще поныне получить от вас и проектов тем крепостям с сметами… Итак, подтверждая в последний раз, ожидаю скорейшаго отправления от вас проектов и смет…».

Вскоре после образования Новороссийской и Азовской губерний было разработано несколько проектов по их устройству. Они были составлены губернатором Азовской губернии В.А. Чертковым (1726–1793) по поручению Г.А. Потемкина и на основании его рекомендаций. Василий Алексеевич Чертков принадлежал к древнему дворянскому роду. В 1748 г. он поступил на государственную службу и в 1764 г. был произведен в бригадиры с назначением обер-комендантом крепости Св. Елизаветы, построенной по ходатайству сербского генерал-майора Хорвата для защиты сербских переселенцев. В 1771 г. он был пожалован в генерал-майоры и с 1776 по 1782 г. исполнял должность Азовского губернатора, был командиром Днепровской линии, а с 1777 г. — генерал-поручиком поселенных в Азовской губернии регулярных и иррегулярных полков и шефом Пики-нерского Луганского полка. Надо заметить, что В.А. Чертков, кроме хорошего знания обстановки в губернии, обладал и литературным талантом. Его перу принадлежит комедия «Кофейный дом» (1770) и «Обряд при Высочайшем шествии Екатерины II через Харьковское наместничество» (1787).

Проекты, составленные Чертковым, оказали большую помощь Потемкину, показав мнение человека, хорошо знакомого с местными проблемами. Начиная государственную деятельность, Потемкин еще не имел сформировавшейся собственной канцелярии, и Чертков стал одним из первых его сподвижников, творчески воплощая распоряжения и предлагая нововведения. Дальнейшая карьера губернатора Азовской губернии сложилась удачно. В 1782 г. Василий Алексеевич был назначен генерал-губернатором Воронежского и Харьковского наместничеств и в 1787 г., в день торжественного посещения Харькова императрицей Екатериной II, пожалован брильянтовым перстнем и 6000 руб. на подъем во вновь вверенную ему Саратовскую губернию.

К сожалению, проекты Черткова не датированы, поэтому нельзя однозначно говорить о том, что первично: его предложения или план Потемкина? Скорее всего, это было творческое развитие идей двух талантливых личностей.

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

Его второй проект, подготовленный совместно с губернатором Н. Языковым, — «Учреждение оборонительное или военное, относящееся к страже и обороне границ», посвящен обеспечению безопасности границ Азовской губернии. Для «соблюдения внутренняго спокойствия» губернаторы считали первоочередным содержать в оборонительном состоянии границу с крымскими и кубанскими татарами по рекам Конские Воды, Берде и Ее. Для этого необходимо кроме уже строящихся крепостей на Днепровской линии перегородить реки плотинами через пять или семь верст между крепостями, а также и в Таганрогском уезде, поселить слободы из определяемых к переходу из России однодворцев. «На случай, естли б каким ни есть образом, — говорилось в 5-м пункте плана, — какия-либо хищники сквозь таковую линию прокрались во внутренности, смежно с теми государственными селениями, основать таковые же однадворческих с равным укреплением четырнадцать пятидесятдворовых слобод». Поселенные таким образом однодворцы должны были снабжаться порохом и амуницией, чтобы в случае «нужды» составить пехотную ландмилицию (поселенные войска), «удобную к отражению всяких набегов». Губернаторы подробно перечисляли, какие полки следует расположить в крепостях и селениях по Днепровской линии, «все ети воинския команды не токмо будут содержать пограничную стражу и обуздают неистовыя предприятия хищников, но в случае каких-либо безпокойств составят в обеих частях нарочитыя деташаменты, кои сами собою, особливо безпорядочно толпамы воюющим, не только достаточно сопротивляться, но и сильной отпор зделать», — считали авторы «Учреждения».