В декабре того же 1862 года произошла очень важная для Кавказа перемена в составе его высшей администрации. Наместник князь Барятинский по расстроенному здоровью вышел в отставку, а его пост занял августейший брат государя императора, его императорское высочество великий князь Михаил Николаевич, на долю которого и выпало окончательное замирение Кавказа. Новому наместнику вскоре после своего прибытия в 1863 году на Кавказ пришлось руководить военными действиями. Возмутились племена, жившие в устье Кубани и на берегу Черного моря.

Против них были направлены Адагумский и Пшехский отряды, предводимые лично его императорским высочеством. Были пройдены земли шапсугов и убыхов. К осени оба этих племени соединились и с прежней яростью попробовали было кинуться на русские укрепления. Они были всюду отбиты, но тогда составился союз из всех непокоренных еще горских племен. Выборные этого союза предполагали послать посольства в Турцию, Францию, Англию с просьбою о защите против России, но среди них не нашлось никого, кто мог бы принять на себя такую задачу, и мысль о посольстве была оставлена. Это было в октябре 1863 года. К Евдокимову явились черкесские старшины и подписали договор, согласно которому все изъявлявшие покорность племена должны были не позже 1 февраля 1864 года переселиться на указанные им места. От выражения покорности отказались только шапсуги и убыхи, занимавшие земли между Главным хребтом и Черным морем. Тогда граф Евдокимов направил на них Даховский отряд, которым командовал генерал Гейман. Отряд пошел в феврале 1864 года с реки Пшиш на Туапсе. Евдокимов сам находился при нем. Был пройден труднейший Гойхтский перевал. Горцы оказывали отчаянное сопротивление, но русские всюду разбрасывали их. Из Туапсе отряд пошел берегом моря к Сочи. У реки Годлик произошло 19 марта последнее сражение, в котором горцы опять были разбиты. Вскоре русские заняли округ Ахчипсхоу на южных склонах Кавказа, последнюю область, дотоле не подчинявшуюся России. Теперь на Кавказе не оставалось и пяди земли, которая не принадлежала бы Российской империи. Кавказ был покорен, перед силою русского оружия пала гигантская, созданная самою природою крепость, пала после шестидесяти лет упорного сопротивления…

21 мая 1864 года на поляне Кбаада, в округе Ахчипсхоу, собралось русское воинство во главе со своими победоносными вождями и августейшим наместником края, и был отслужен благодарственный молебен по случаю окончания титанической борьбы.

Много племен, а шапсуги почти все поголовно, переселились в Турцию. Их земли были заняты частью казаками-переселенцами, частью мирными племенами, в верности которых не могло быть сомнения. В 1865 году был учрежден Кавказский военный округ, и началось гражданское устройство Кавказского наместничества.