Операциями против Шамиля руководил Александр Иванович Барятинский
, аристократ, личный друг Александра II, но и старый кавказец, начавший воевать здесь с 1835 г., командуя черноморской казачьей сотней. В 1856 г. он стал главнокомандующим. Ну а непосредственно обеспечил победу Николай Иванович Евдокимов. Сын солдата и казачки, он родился в Наурской, был отдан в школу кантонистов. Рядовым солдатом совершил серьезный проступок, удрал из расположения полка. В лесу обнаружил собиравшихся для нападения горцев, вернулся в часть и провел отряд к этому месту, после боя был не только прощен, но и произведен в прапорщики. В сражении у Бурной остался единственным офицером в роте, получил рану в лицо, за что горцы прозвали его «Уч-гезы» — «Трехглазый». В 1843 г. прославился походом своего маленького отряда на аул Унцукль. Разгромив войско Хаджи-Мурата, попытался по-хорошему поговорить с местными. Но на него бросился фанатик, ранив кинжалом. Евдокимов выхватил шашку и развалил его надвое — и вот это подействовало, горцы его зауважали. Потом был командиром Волгского казачьего полка, возглавлял экспедиции, дослужился до генерал-лейтенанта. И стал начальником левого фланга.Барятинский и Евдокимов методично оттесняли Шамиля в высокогорье. Начали выражать лояльность и чеченские общины. Их переселяли на равнину, отрывая от мюридов. Имам злился, нападал на изменившие ему дагестанские и чеченские аулы. Но это ему только вредило, он приобретал кровных врагов, а русские, помогавшие горцам защититься от мюридов, становились союзниками. В 1856–1858 гг. удалось замирить большую часть Чечни. Были вырублены самые дикие места, Маюртупский орешник, леса по р. Аргун, просека дошла почти до Ведено. В 1858 г. Евдокимов взял штурмом Шатой. Шамиль укрылся в Ведено. Но и сюда пришел отряд Евдокимова. В апреле 1859 г. Ведено было захвачено и сожжено. Имам ушел в Аварию. Там его настигла экспедиция генерала Врангеля. Войско Шамиля начало разбегаться, сам он с небольшим отрядом ушел в Гуниб, где и был осажден. Сюда прибыли Барятинский и Евдокимов. Предложили сдаться на условиях свободного выезда в Мекку. Шамиль отказался, готовился к обороне, заставил носить камни на укрепления даже своих жен и невесток. Тогда русские пошли на штурм и взяли первую линию обороны. Имам заперся в замке, окруженный со всех сторон. И после переговоров все же капитулировал. 8 сентября Барятинский отдал приказ: «Шамиль взят, поздравляю Кавказскую армию!»
Восточный Кавказ был усмирен. Барятинский за это получил орден св. Георгия II степени, Евдокимову царь пожаловал графский титул и чин генерала от инфантерии, Бакланову, занимавшему должность походного атамана донских казаков на Кавказе — генерал-лейтенанта. Оставался Западный Кавказ. Это обстоятельство привело к реорганизации казаков. В 1860 г. «для большего единства управления, сообразно с новым положением Северного Кавказа и общею системой администрации» Кавказское Линейное Войско было разделено надвое. Шесть правофланговых бригад объединялись с Черноморским Войском и составили Кубанское Войско. Центром его стал Екатеринодар. А четыре левофланговые бригады составили Терское Войско с центром во Владикавказе. Таким образом достигалась централизация командования теми казачьими частями, которые прикрывали еще не замиренную часть Кавказа. И вдобавок получалось деление казаков, близкое к традиционному — по рекам.
Покорение Западного Кавказа возглавил Евдокимов. Здесь были сосредоточены лучшие силы и развернулось систематическое наступление, так же, как на Шамиля. В 1860 г. было подавлено сопротивление черкесов по рекам Илю, Убину, Шебшу, Афипсу. И рубежи были вынесены вперед, началось строительство Белореченской линии по р. Белой. Вместе с линией по Кубани и Черноморской береговой линией получалось почти замкнутое кольцо, зажавшее область «немирных» горцев. В 1861 г. в урочище Чхафизапс на Белой было разгромлено местное ополчение, пытавшееся помешать строительству. В 1862 г. отряды солдат и казаков продвинулись вверх по Белой, Курждипсу и Пшехе. Мирных черкесов Евдокимов отселял на равнину — живи, хозяйствуй, торгуй с русскими. Ну а на тех, кто продолжал враждебные действия, обрушивалась суровая расплата.
Сказался еще один фактор. Турция задумала создать собственное подобие казачества, башибузуков, и поселить среди подвластных христианских народов, чтобы держать их в повиновении. А после Крымской войны, когда исчезла надежда прорваться к Кавказу, в Стамбуле вызрел проект привлечь в башибузуки черкесов. К ним засылались эмиссары, вербуя переселяться в Турцию. Считалось, что они действуют тайно. Но Евдокимов через свою агентуру прекрасно об этом знал. Однако не препятствовал, а наоборот, поощрял. Уходили-то самые энергичные, воинственные, непримиримые — ну и скатертью дорога! Русские посты закрывали глаза, когда караваны двигались к турецким границам или грузились на суда, войска отводились в стороны с пути их следования.