Но военного конфликта не случилось, с появлением Шагин-Гирея боевые действия не начались. И выздоровевший Прозоровский вернулся к войскам. По планам Екатерины и Потёмкина, следовало утвердить дружественного России хана Шагин-Гирея на посту главы государства, уже не являвшегося вассалом Оттоманской Порты и пока не вошедшего в Российскую империю.
Вооружённые отряды противников Шагин-Гирея сновали по Крыму. Это было своеобразное продолжение Русско-турецких войн. Стамбул стремился передать власть в Крыму Девлет-Гирею — брату ставленника России. Воцарение Шагин-Гирея было своеобразной военной операцией, в которой Суворов сыграл центральную роль. Прозоровский вверил Суворову крупное соединение — в него вошли Орловский и Ряжский полки, Ахтырский гусарский и Чугуевский казачий полки, два гренадерских батальона, сотня казаков-донцов, четыре орудия. С этим войском Суворов выступил в утомительный, но по-суворовски скорый поход из Перекопа к Крымским горам.
Девлет-Гирей с войском стоял в районе Карасу-Базара. Суворов продемонстрировал противнику свою силу, выслав к Карасу-Базару небольшой кавалерийский отряд. Психологический ход возымел действие. Отряд Девлета был рассеян от одного вида русских конников, а сам хан, ставленник Стамбула, бежал в Кафу (современная Феодосия). Из Тамани, вместе с русским отрядом генерала де Бальмена, в Еникале прибыл Шагин-Гирей. Мурзы, один за другим, переходили на его сторону. Суворов на берегу Булзыка объявляет Шагин-Гирея ханом, а затем очищает от враждебных сил крепость Кафу. На штурм крепости Суворов отрядил Ряжский пехотный полк под командованием полковника А.Я. Шамшева. Авангард майора Ушакова занял крепость 20 марта, действовали ряжцы быстро, проворно, выученно, с полуслова понимая своего командира. А на следующий день к двум ротам Ушакова присоединились другие части Ряжского полка.
И на этот раз Суворов обходится без кровопролития: войска Девлета, завидев передовые русские части, морем бежали в Турцию. Бежал и сам хан Девлет-Гирей. Шагин-Гирей занял Бахчисарайский дворец, верховный диван провозгласил его правителем, лишив власти Девлет-Гирея. Как и требовалось России, Шагин-Гирей попросил оставить в Крыму русский гарнизон, имея в виду, в первую голову, полюбившегося ему Суворова. В июне 1777-го Суворов уже считал службу в Крыму видом бездеятельного прозябания и просил Потёмкина о перемене места службы, даже съездил в Полтаву, в отпуск, для встречи с женой. В отпуске Суворов приболел, для лечения на месяц поселился в Опошне. Между тем обстановка и в Крыму, и на кавказском побережье складывалась непростая: на полуострове сохранялась опасность выступления протурецки настроенных крымских мурз, а на Кавказе турки укрепляли крепости Анапу и Суджук-Кале.
29 ноября 1777 г. Суворов получает ордер Румянцева «ехать для принятия команды над корпусом на Кубани относительно дел татарских и взаимного сношения поступать».
Граница империи проходила на Кавказе по Кубани. Там, в Копыльском ретраншементе (позже — станица Славянская), он принял командование над Кубанским корпусом у генерал-майора И.Ф. Бринка, чьи неспешные действия вызывали ярость Румянцева. В Копыльском Суворов осмотрел войска и долго беседовал с Бринком о здешних делах.
На Кубани Суворов возьмёт за правило много ездить, перемещаться, изучая район, который прежние командиры знали главным образом по картам. Суворов лично, с небольшим казачьим отрядом, осмотрел границу по берегам Кубани и Азовского моря. Однажды отряд был обстрелян «закубанцами». Кочевавшие на Кубани орды ногайских татар в основном признавали власть Шагин-Гирея и относились к России дружественно. Заправляли в ногайских ордах братья бахчисарайского хана — Арслан-Гирей и Батыр-Гирей. Суворов встречался с ними и с другими вождями ногайцев, некоторые из них по личной инициативе являлись на поклон к русскому генералу. Суворов приметил двойную игру Батыр-Гирея, который ориентировался на Турцию, хотя в личных беседах уверял Суворова в приверженности России… В воздухе пахло порохом. В приграничных землях энергия Суворова нашла применение. Какое-то время Суворову пришлось бороться со слухами о смерти Шагин-Гирея. По требованию Суворова Шагин-Гирей прислал из Бахчисарая свои указы-фирманы в орды ногайских татар, удостоверяя свою власть.
Две укреплённые линии защищали границу — Моздокская (здесь стояли регулярные части) и Терская (на этой линии границу защищали казачьи войска). Суворов въедливо проинспектировал укрепления и пришёл к выводу о необходимости третьей линии — Кубанской, которая защищала бы границу к западу от Ставропольской крепости.
Весной 1778 г. в разгаре были фортификационные работы. Более энергичного строителя укреплений, чем Суворов, российское приграничье не знало. В двух «работных армиях» трудились 700 человек; они возвели десять крепостей и девятнадцать фельдшанцев. Ачуев, Темрюк, Тамань, Усть-Лабинский, Духовный — эти укрепления отныне защищали подходы к плодородной Кубани. Суворов — отец-основатель этих будущих городов и посёлков. Для эффективного управления укреплениями Суворов разделил линию на шесть дирекций. Лично объезжал объекты, въедливо инспектировал строительство, вникая в мелочи. Он писал Румянцеву о кубанских укреплениях — о реализованных и предполагаемых планах: «Крепости и фельдшанцы по Кубане прострились нечто и за Тамишберг с неожидаемым успехом. Они столько неодолимы черкесским поколениям по их вооружению, что становились им совершенно уздою, были б они доведены в смычку Моздокской линии к Ташле к половине апреля. Коммуникационные ж полегче редуты внутрь земли кончились бы около половины мая и послужили б к содержанию ногайцев в приличности. Укрепления сил по Кубане, сильнее почти обыкновенных линейных, могли бы современем переименоваться в линию…». В каждой крепости, в каждом укреплении побывал Суворов, проверяя надёжность построек.
Тем временем в Крыму снова начались волнения. Татарские мурзы поднялись против Шагин-Гирея, желая заменить его Селим-Гиреем, сыном двуличного Батыр-Гирея, того самого, с которым Суворов познакомился на Кубани. Мятеж, с помощью Прозоровского, был подавлен. Но в Петербурге были недовольны нерасторопностью князя, которому присвоили очередное звание генерал-аншефа, и направили в спокойный Орёл генерал-губернатором. Такова была идея Потёмкина. 23 марта 1778 г. командующим Крымским корпусом был назначен генерал-поручик Суворов, который в то время уже пользовался безграничным доверием Потёмкина. Крым нужно было оборонять от турок: и Потёмкину требовался деятельный командующий, который бы объединил Крым и Кубань как единый оборонительный фронт. Строились крепости, ретраншементы, фельдшанцы. Обустраивались укреплённые казаками почтовые станции. Воинские посты располагались в трёх верстах один от другого. Казаков в Крыму было уже немало, несколько тысяч. Крым обрусевал. Следовало укреплять Кинбурн, защищавший Крым со стороны сильнейшей турецкой крепости — Очакова.
В бухте Ахтиар стояла турецкая эскадра — 14 вымпелов, под командованием Гаджи-Мегмета-аги. На судах обосновался десантный отряд из семисот янычар. Они должны были поддержать Селим-Гирея. Эскадра не ушла и после провала мятежа. Время от времени турки совершали дерзкие вылазки в Крым. Под Херсонесом был убит выстрелом в спину и ограблен донской казак. Суворов ответил на это строгим письмом Гаджи-Мегмету. Одними угрозами и ультиматумами Суворов не ограничился. На берегах Ахтиарской бухты русские солдаты начали фортификационные работы. Теперь турецкой эскадре угрожали батареи. Гаджи-Мегмет поступил благоразумно: отплыл от крымских берегов и встал на якоря в трёх верстах от гавани. Началась переписка Суворова с Гаджи-Мегметом, в которой турецкий капудан-паша отстаивал право османского флота причаливать к берегам Крыма. Суворов был непреклонен, указывая на самостоятельность крымского ханства, которое при Шагин-Гирее фактически попало под власть Петербурга. В итоге Суворов перекрыл источник пресной воды турецкой эскадры — устье Бельбека. Вооружённый русский отряд теперь не пускал турок к источнику… Эскадра Гаджи-Мегмета ушла к турецким берегам, в Синоп.