В следующем году близ главного аула казикумыков Андреевского — по-чеченски Эндери, центра работорговли, — была выстроена крепость Внезапная, соединённая с Грозной рядом укреплений. Лесные дебри сделались доступными русским солдатам. Большая часть жителей богатых аулов Андреевского и Костековского, имевших сношения с аварским ханом, изъявили покорность России. Как доносил Ермолов императору 7 июня 1818 года, «строгим настоянием моим и усердием старшего владельца прекращён (в Андреевской) торг невольниками, которые свозились из гор и дорогою весьма ценой продавались в Константинополь.
Большая часть таковых были жители Грузии…»
С неумолимой последовательностью, планомерно двигался Ермолов на воинственные горские племена. «Они противятся, — сообщал он бывшему инспектору артиллерии Меллер-Закомельскому. — С ними определил я систему медления и, как римский император Август, могу сказать: „Я медленно спешу“.
Привыкшие к тому, что русские задабривают их, горцы пробовали и с новым главнокомандующим вести прежнюю политику выманивания подачек. Когда Ермолов находился с посольством в Персии, чеченцы захватили полковника Шевцова и потребовали за него выкуп в восемнадцать телег серебра. Но Ермолов был не Тормасовым и не Ртищевым.
Собрав старшин чеченских аулов, главнокомандующий объявил им, что все они будут повешены, если к назначенному сроку пленник не будет возвращён. Горцы поняли, что грозный Ярмул слов на ветер не бросает, и Шевцова привезли в целости и сохранности.
Однако, видя на примере Чечни угрожающую им опасность, юрская знать спровоцировала в 1818 году против русских восстание. Местные феодалы попытались создать для борьбы с Россией союз горских народов. К этому союзу присоединились внутренние ханства — Аварское и Казикумыкское, так называемое вольное Акушинское общество, а также области, примыкавшие к Каспийскому морю, — Мехтула, Каракалдаг и Табасарапь. Правители Дагестана старались привлечь на свою сторону также шамхальство Тарковское на севере и Кюринское ханство на юге, некогда отторгнутые от Казикумыка и оставшиеся верными России.
Из-за недостатка войск Ермолову приходилось действовать поочерёдно в разных провинциях: летом — в Чечае и Казикумыкской области, зимой — в Дагестане. Природа превратила Дагестан в необычайно сильную укреплённую крепость. Особенно неприступной была Авария, лежавшая в центре свободных дагестанских обществ. В 1819 году в покорённое уже русскими Кубинское ханство прибыл генералмайор Мадатов. Поводом для вторжения в Дагестан явились попытки аварского хана Султан-Ахмеда оказать помощь чеченцам. Мадатов без пролития крови покорил Табасарань и всчед за тем проник в уцмийство Каракалдагское. Нижний, то есть равнинный, Каракалдаг покорился русским добровольно, но уцмий Адиль-Гирей укрепился в Верхнем, нагорном, Каракалдаге — столице своих владений ауле Башлы. 5 октября Башлы был взят штурмом, а 20-го Мадатов разгромил главные силы уцмия. После этого весь Каракалдаг признал себя подвластным России.
В то время, когда Мадатов действовал с юга, Ермолов шёл на Дагестан с севера. Ещё до появления Мадатова горцы разбили высланный против них небольшой отряд генерала Пестеля и произвели ряд нападений на шамхальсгво Тарковское. В особенности непримиримыми были мехтулинцы, хан которых — Гассан — был личным врагом тарковского шамхала. Неприятель встретил Ермолова на Аскорайских высотах, и у Талгинской горы произошёл кровопролитный бой. В нём особенно отличился Шевцов, которого Ермолов вызволил из плена. Лезгины были сбиты с гор и освободили проход в Мехтулу.
Ермолов повёл войска на аул Большой Джангутай. В это время на помощь мехтулинцам прибыли акушинцы, одно из храбрейших лезгинских племён. После нового боя Джангутай был взят русскими. Мехтулинский хан был лишён своего владения. Так же поступил Ермолов и с аварским ханом, который обратился к русскому главнокомандующему с просьбой о примирении.
Затем Ермолов двинулся в самые недра гор, на вольный Даргинский союз, лежавший между Каракалдагом, Казикумыком и Мехтулой, по берегам рек Кара-койсу и Кумыкское-койсу. Здесь собрались и аварский и мехтулипский ханы, и Ших-Али Дербентский, получавший помощь от Персии, и уцмий каракалдагский. Во главе даргинцев стояли акушинцы, самое могучее из союзных обществ, некогда разгромившее войско самого Надир-шаха.
Ермолов предупредил акушинцев, что они будут прощены, если останутся спокойными и выдадут всех укрывшихся у них мятежных ханов, но те ответили отказом.
Тогда главнокомандующий, приказав Мадатову наступать с юга, сам с севера двинулся в глубь Дагестана. Акушинцы ожидали русских у горной реки Макасе. 19 октября 1819 года здесь произошёл бой, закончившийся полным разгромом горцев.
Союз распался: казикумыки, койсубулинцы и мехтулинцы оставили даргинцев. Ермолов прошёл через всё вольное Акушинское общество, являя подчинённым пример неустрашимой личной храбрости, которая производила огромное впечатление и на горцев, умевших ценить мужскую доблесть.