Покончив с Чечней, Ермолов принялся за Нагорный Дагестан.

Дагестан и этому герою представлялся неприступною крепостью. В особенности неприступною была Авария, лежавшая в центре свободных дагестанских обществ. Ермолов поставил себе задачей если не покорить, то сделать Дагестан совершенно безопасным для русских, и вот начались передвижения войск вскоре после того, как на страже Дагестана появилась крепость Внезапная. В 1819 году в покоренное уже русскими Кубинское ханство прибыл один из самых храбрейших сподвижников Ермолова, генерал-майор князь Мадатов. В Кубе в то время стоял небольшой отряд генерала Пестеля. Мадатов же, происходивший из знатного рода карабахских армян, был в то время окружным начальником ханств – Шекинского, Ширванского и Карабахского. Поводом к вторжению в Дагестан были попытки аварского хана Султан-Амеда оказать помощь чеченцам. Мадатов без пролития крови покорил Табасарань и вслед за тем проник в уцмийство Каракайдагское. Нижний Каракайдаг (то есть равнинный) покорился русским добровольно, но уцмий Адиль-Гирей укрепился в Верхнем (нагорном) Каракайдаге, в столице своих владений ауле Башлы. 5 октября Башлы были взяты Мадатовым штурмом, а 20-го были разгромлены главные силы уцмия, укрепившиеся на горах около аула Сумси. После этого погрома весь Каракайтаг признал себя подвластным России. В то время, когда Мадатов действовал с юга, сам Ермолов шел на Дагестан с севера. Еще перед появлением Мадатова горцы разбили высланный против них отряд Пестеля и произвели ряд нападений на шамхальство Тарковское. В особенности непримиримыми были мехтулинцы, хан которых Гассан был личным врагом тарковского шамхала. Ермолов решил, что Мехтуле первой придется пасть под его ударами, и вошел в ее пределы. Неприятель встретил его на Аскорайских горах, и у Талгинской горы произошла кровопролитная битва. В ней особенно отличился Швецов, тот самый офицер, которого Ермолов вызволил из плена. Лезгины были сбиты с гор, и проход в Мехтулу был свободен. Ермолов повел войска на аул Большой Дженгутай, а в это время к мехтулинцам прибыли на помощь акушинцы, одно из храбрейших лезгинских племен Дагестана. Произошла новая битва, и Дженгутай был взят русскими. Мехтулинский хан был лишен владения и объявлен изменником, так же поступил Ермолов и с аварским ханом, попробовавшим было просить русского вождя о помиловании.

Разгром Мехтулы предшествовал покорению Каракайтага и Табасарани. Когда Мадатов покончил с ними, Ермолов двинулся далее, в самые недра гор, на вольный Даргинский союз, лежавший между Мехтулой, Каракайдагом, Казикумыком и Андалялем по берегам рек Кара-Койсу и Кумыкского Койсу. Так или иначе, уничтожить это гнездо было необходимо. Здесь собрались и аварский, и мехтулинский ханы, и Шир-Али дербентский, действовавший при помощи Персии; сюда же укрылся уцмий каракайдагский. Во главе даргинцев стали акушинцы, самое могучее из союзных обществ, и к ним примкнули казикумыки со своим яростным противником русских Сурхай-ханом. Вместе с казикумыками были койсубулинцы. Мехтула позабыла о недавнем погроме и тоже поднялась на покорителей; взволновались даже Тарки, и в шамхальстве поднялся мятеж, усилившийся после того, как под Тарки подошли мехтулинцы.