С завершением Крымской войны на Кавказе была сосредоточена 220-тысячная армия. Все ее генералы, начиная с Барятинского и начальника главного штаба Кавказской армии (в нее был преобразован отдельный Кавказский корпус) Д.А. Милютина, имели опыт горной войны, научились использовать численный перевес и превосходство современного стрелкового оружия. По указанию нового наместника воевали не только штыком, но и топором: рубили просеки, повышавшие маневренность войск, защищали их новыми крепостями. Барятинский нашел и еще один важный резерв: не останавливаясь перед подкупом, он повел дружелюбную политику в отношении мирных горцев, укрепляя тем самым свои позиции и ослабляя противника.
«Шамиля, – писал современник, – всегда сопровождал палач, а Барятинского – казначей, который тут же награждал отличившихся главарей и предводителей золотом и драгоценными камнями». В результате сочетания силовых и дипломатических средств давления на противника русским к 1859 г. удалось подчинить всю равнинную Чечню и восток Дагестана.
Напрасно взывал к уставшим от войны чеченцам Шамиль. С взятием 1 апреля 1857 г. его горной резиденции аула Ведено от некогда обширного имамата осталось лишь несколько районов горного Дагестана.
Чувствуя, что борьба вступает в решающую фазу, Барятинский выехал непосредственно к войскам. Вместе с начальником штаба – будущим фельдмаршалом Милютиным он подготовил мощную наступательную операцию против последнего прибежища имама. Финал трагедии разыгрался в августе 1859 г. у дагестанского аула Гуниб. Скала, где он был расположен, представляла из себя природную крепость, к тому же укрепленную по всем правилам военной фортификации. И тем не менее отряд из 400 человек, которым располагал имам, конечно, не мог сдержать подавляющую силу царских войск. 18 августа Барятинский предложил Шамилю сдаться, обещая отпустить его в Мекку с теми, кого пожелает взять с собой. Имам отказался, не поверив в искренность русского полководца, и с вызовом заявил: «У меня есть еще в руке шашка – приди и возьми ее!».
Тогда рано утром 25 августа начался решительный штурм. В самый разгар боя, когда осажденных осталось не более 40 человек, и они готовились подороже продать жизнь, огонь неожиданно прекратился: Барятинский вновь предложил почетную сдачу. Шамиль был убежден в коварстве «неверных», но отказ сыновей от дальнейшего сопротивления и уговоры соратников не подвергать гибели женщин и детей сломили старика.