В лице нового наместника край получил такого правителя, который являлся в него не новичком, а хорошо знакомым со всеми местными условиями и особенностями. При этом Барятинский искренне желал покончить с Кавказом. Он, понимая, что одному ему ничего не удастся сделать, прежде всего учредил пост отдельных командующих войсками, облеченных правами корпусных комендантов. Начальником своего штаба, то есть ближайшим своим помощником, он избрал и тогда уже пользовавшегося громкою известностью генерала Д. А. Милютина. Способ войны остался прежним: правильная осада гор, прокладка дорог и очищение местности от непроходимых лесов. В Чечню, на которую главнокомандующий обратил особенное внимание как на область с неукротимым хищным населением, им назначен был опытный кавказский воин, начальник левого фланга линии генерал Евдокимов. Вновь были заняты оставленные в Восточную войну Анапа, Новороссийск и Сухум-Кале и возобновлены уничтоженные укрепления на Черноморском побережье. Но главное внимание наместник все-таки пока отдавал Чечне. Шли, правда, медленно, но зато совершенно верным путем. За два года, 1856-й и 1857-й, были достигнуты очень крупные успехи. На правом фланге занята Адагумская равнина и возведено укрепление Майкоп. На левом фланге от Владикавказа проложена укрепленная дорога параллельно хребту так называемых Черных гор до Куринского укрепления на Кумыкской плоскости. Почти вся Чечня была подчинена установленному Барятинским и Милютиным военному управлению; на землях сильнейшего из чеченских племен – ауховцев – развилось сильное русское укрепление; была возвращена Салатавия; на Лезгинской линии истреблением лесов были уничтожены разбои. В 1858 году генерал Евдокимов прошел считавшееся неприступным Аргунское ущелье и заложил сильное укрепление на реке Аргун, от имени реки названное Аргунским. После того были покорены шатоевцы, и на их землях была заложена крепость Евдокимовская. Одновременно с Евдокимовым, действовавшим в Чечне, из Прикаспийского Дагестана двигался в горы отряд генерала Врангеля, а с Лезгинской линии – отряд генерала барона Вревского. К концу

1858 года Черные горы были пройдены русскими, а Чеченская плоскость вся очищена от мятежников…

Стесненный Шамиль бросался из стороны в сторону, стараясь вновь сплотить горцев, но все его попытки оставались тщетными. Желая отвлечь русских, имам с остатками своих дружин ударился было на Назрань, но тут он был разбит генералом Мищенко. Тогда Шамиль ушел в свой аул Ведено, но Евдокимов явился и сюда. 17 марта

1859 года была начата осада последней столицы мюридов, и 1 апреля аул Ведено был взят. Шамиль бежал, но теперь дни его были сочтены.