Осуществление этой задачи было возложено на «государева наместника Азовского и Астраханского» генерал-аншефа князя Г. А. Потемкина. По его распоряжению военные специалисты составили карты и описание пограничья. В итоге князь представил Екатерине II доклад о сооружении десяти крепостей от Азова до Моздока.
Доклад получил одобрение императрицы, и 24 апреля 1777 г. последовал высочайший указ о строительстве Азово-Моздокской линии. Откроем Полное собрание законов Российской империи и процитируем текст:
Первоначально имелось два варианта проектируемой линии. В «Докладе» и в «Описании линии» характеристика крепостей давались в применении к первому варианту проекта, что отражено и на карте. Фактически же строительство осуществлялось по второму варианту, причем было построено не десять, а девять крепостей. Первоначально проектировавшаяся в верховьях Бийбалы (Мокрой Буйволы) крепость № 6 в вышедшем 20 мая 1777 г. приказе Г. А. Потемкина уже не упоминалась:«Сия линия имеет простираться от Моздока к Азовской губернии в следующих местах, где построя новые укрепленные селения, коим примерный план у сего представляется, а именно: 1) на Куре, 2) на Куре ж, 3) на Цалуге, 4) на Куме, где и Командир вышеписаных укреплений квартиру свою иметь должен; 5) на Томузлове, 6) на Бийбале, 7) на Калаусе, 8) на Ташле, 9) на Егорлыке, 10) в главном укреплении от Черного леса к Дону, где квартира второй части Командиру должна быть…» (СПб., 1830. – Т. 20. – № 14.607. – С. 519).
«Учреждаемые по линии от Моздока к Азову селения наименовать: 1-е Святыя Екатерины, 2-е Святого Апостола Павла, 3-е Святыя Марии, 4-е Святого Георгия, 5-е Апостола Андрея, 6-е Святого Александра Невского, 7-е Ставрополь...»
Для сооружения крепостей и несения службы в гарнизонах на Кавказ переселили волжских и донских казаков. Прикрывали строительство регулярные воинские части: Владимирский драгунский и Кабардинский пехотный полки, два батальона егерей и несколько казачьих полков с Дона. Все они были сведены в Астраханский корпус. Его командиром и руководителем строительства Азово-Моздокской линии стал генерал-майор Иван Варфоломеевич Якоби.
По приказу генерала И. В. Якоби 5 октября 1777 г. Владимирский драгунский полк с хоперскими казаками выступил к «Черному лесу на урочище Ташлу и Калаус». К исходу первой половины осени полк прибыл к истокам Ташлы, а 22 октября (по новому стилю 4 ноября) 1777 г. была заложена крепость № 7.