Барятинский, правою рукой которого в звании начальника штаба армии был генерал Д. А. Милютин, впоследствии ставший военным министром, приступил к решительным действиям. Он разработал детальный план продвижения от рубежа к рубежу с прочным закреплением занятых территорий. Наступление на Шамиля велось в основном со стороны Чечни.
Завоевав какую-либо местность, русские устраивали здесь казачьи поселения — станицы, делали в вековых лесах широкие просеки, пролагали дороги, и, устроив край, двигались далее в дебри Дагестана.
Все действия первоначально были направлены на Восточный Кавказ и велись одновременно с 3-х сторон: Н. И. Евдокимов последовательно занимал позиции в Чечне; А. Е. Врангель — давил на правый фланг Шамиля, со стороны Дагестана; И. А. Вревский — в тыл горцам, со стороны Лезгинской линии74.
Шамиль засел в труднодоступном ауле Веден, долгое время являвшемся его резиденцией. Поэтому все усилия русских войск сосредоточились на том, чтобы занять этот аул. Летом 1857 г. начальник левого фланга Кавказской линии генерал Н. И. Евдокимов начал наступление в Малую и Большую Чечни, затем в Аух. Продвижение русских войск в этих областях сопровождалось упорными и ожесточенными боями. И русские, и горцы сражались, как львы. За последние годы счастье окончательно отвернулось от Шамиля: у него не стало Хаджи-Мурата, Ахверды Магома, Шуаиб-муллы, этих самородков-полководцев, изумлявших своею энергией, отвагой, быстротою и внезапностью налетов, умением держать в руках и воодушевлять к отчаянному бою толпы непривычных к дисциплине горцев. Дух населения, религиозный фанатизм, его вера в свое боевое превосходство, в неприступность лесов, исчезли. Страшные потери лучших людей и разорения последних лет посеяли уныние. В то же время силы русских войск утроились. Преувеличенная осторожность и опасливость исчезли. Старые промахи научили другим приемам. Появилась система в действиях75.
В январе 1858 г. Евдокимов прорвался в Аргунское ущелье, взяв приступом завалы, нагроможденные горцами против него, и оказался у Ведена. 1 апреля 1859 г. пал Веден, бывший в течение 14 лет средоточием враждебной русским силы76. Однако Шамиль сумел скрыться.
Со взятием Ведена было утверждено окончательно завоевание всего края по северному склону Айдийского хребта. Кроме того, взятие этого укрепления имело весьма большое нравственное значение в крае. Оно сильно поколебало влияние Шамиля.
С падением Ведена пали Чечня и Ичкерия: все население северного склона гор, обращенных к левому крылу Кавказской линии, покорилось77.
Теперь путь в Дагестан был открыт. Русские войска наступали с трех сторон тремя отрядами. Чеченский отряд возглавлялся Н. И. Евдокимовым, Дагестанский — бароном А. Е. Врангелем и Лезгинский — князем Л. Е. Меликовым. Общее руководство осуществлял Барятинский, 14 июля прибывший в Чеченский отряд78. Об успешных действиях свидетельствуют приказы главнокомандующего. 21 июля в лагере при озере Решло Барятинский обратился к войскам Дагестанского отряда: «...вы храбро заняли переправу через Койсу и тем блистательно исполнили мое желание; благодарю вас от всего сердца за ваш подвиг». 27 июля снова победа. В Андии, близ аула Тоидо, он объявил: «Сегодня доношу я государю императору о покорении его державе Аварии, Койсубу, Гумбета, Салаватии, Андии, Технуцала, Чеберлая и других верхних обществ.
Благодарю войска Дагестанского и Чеченского отрядов, всех, от генерала до солдата, за столь радостную весть для сердца возлюбленного монарха». 6 августа близ аула Канхадатль новая благодарность главнокомандующего: «В бессмертном подвиге покорения Восточного Кавказа самая тяжелая доля трудов предстояла вам, войска Лезгинского отряда. Вы совершили с самоотвержением предначертания мои и превзошли все ожидания. Примите, братцы, мое душевное спасибо»79.
Пленение Шамиля в Гунибе
После потери Ведена Шамиль устремился на юг и пробрался в горные возвышенности Гуниба (горное плато в Предкавказье высотой до 2354 м). В это время весь отряд его состоял из 400 человек при 4-х орудиях. Засев на вершине Гуниба, Шамиль в основном рассчитывал на недоступность его для русских. Предполагая превратить аул в неприступную крепость, Шамиль велел взорвать порохом все скалы, по которым проходили тропинки в Гуниб. С южной стороны, самой низкой и доступной, были сооружены толстые стены-башни, двух- и трехъярусные оборонительные постройки, заготовлено большое количество камней, чтобы скатывать их, если бы русские стали брать аул штурмом.