Пока Суворов хворал и отнекивался от службы в Крыму, обстановка там резко осложнилась. Шагин-Гирей в своей политике оказался столь же крутым, как и его брат. Огражденный русскими штыками, он вел себя крайне надменно, не считаясь с национальными обычаями и традициями, проводил реформы на европейский лад, к которым народ не был подготовлен. Хан стал ездить в карете, обедать за столом, сидя в мягких креслах, завел себе повара-француза. Все его затеи требовали больших денег, между тем кошелек его был пуст. Повышение налогов вызвало ропот, а отдача части доходов на откуп русским купцам — возмущение. Для простого народа он был вероотступником, в глазах вельмож — изменником. Не брезгуя ничем, противники Шагин-Гирея даже распустили слухи о том, что он принял христианство под имением Ивана Павловича. Вспыхнувшее восстание, во главе которого встал его брат Селим, заставило хана бежать в русский лагерь. Разъяренные мятежники разграбили все сокровища дворца Шагина и изнасиловали женщин его гарема. Нерешительность Прозоровского привела к тому, что восстание стало бурно развиваться, угрожая находившимся в Крыму русским отрядам. И хотя в решающем сражении в октябре 1777 года татары были наголову разбиты, потеряв убитыми и ранеными до двух тысяч человек, волнения не унимались и даже перекинулись из Крыма на Кубань.

5 января 1778 года Суворов принял Кубанский корпус.

Прежде всего он позаботился о независимости от Прозоровского, которому подчинялся его предшественник генерал-майор Бринк. Обратившись с рапортом к главнокомандующему армиями в Крыму и на Кубани Румянцеву, Суворов объяснил свое ходатайство как «немалой от Крымского полуострова от здешнего места отдаленности», так и тем, что Прозоровский «в знании здешнего края не весьма достаточен». Отсутствие ответа Суворов воспринял как молчаливое согласие фельдмаршала и в дальнейшем не посылал в Крым никаких донесений. Развязав таким способом себе руки, генерал-поручик энергично принялся за укрепление русских позиций на Кубани, добившись за короткий срок — всего три месяца — поразительных результатов.

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

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

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

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

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

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

Кубанская кордонная линия, возникшая после Кучук-Кайнарджийского трактата, по сути, и явилась границей с Турцией. Помимо усиления существующих военных постов, Суворов предложил протянуть цепь укреплений вверх по Кубани, чтобы сомкнуть ее с уже существующей Моздокской линией, учрежденной еще в 1763 году и предназначавшейся для защиты русских поселений от набегов кавказских горцев из Кабарды и Чечни.

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

Строительные работы велись в тяжелых условиях. Вспоминая это время, Суворов писал правителю канцелярии Потемкина П. И. Турчанинову в своем обычном, образном и афористичном стиле: «Я рыл Кубань от Черного моря в смежность Каспийского, под небесною кровлею, преуспел в один Великий пост утвердить сеть множественных крепостей, подобных мостдокским, не с худшим вкусом. Из двух моих в 700-х человеках работных армиев, строящих оные на носу вооруженных многолюдных варваров, среди непостоянной погоды и несказанных трудов, не было умершего и погиб один — невооруженный». Уже 19 марта Суворов мог донести Румянцеву, что «крепости и фельдшанцы по Кубани построились… с неожидаемым успехом. Они столько неодолимы черкесским поколениям по их вооружению, что становятся им совершенно уздою».