Покорение Аварии отозвалось в этом крае, как и в других. Враждебная Шамилю партия сейчас же выступила вперед; но во главе ее стал не приверженец старины, а один из основателей мюридизма, целый год боровшийся с Шамилем за верховную власть, известный Кибит-Магома. Лишенный официального значения, но чрезвычайно влиятельный в горах, этот человек увлек за собой население Тибитля, одного из главных андалальских аулов, и послал депутацию к генералу Врангелю. Поборники мюридизма были, однако ж, еще сильны в Андалале, и прочие аулы молчали. Исход дела зависел от того, какая партия возьмет там верх. Получив депутацию Кибит-Магомы, барон Врангель немедленно двинул к пределам Андалала князя Тарханова, стоявшего на восточном рубеже Дагестана; но в турчидагском отряде, после занятия стольких пунктов, оставалось очень немного людей. Князь Тарханов, известный своею решительностью, двинулся прямо к Чоху, одной из главных твердынь Шамиля, взбунтовал население аула, заставил мюридов бежать из крепости и ввел в нее русский гарнизон, но Чох поглотил его последние силы; дальше ему не с чем было идти. Другие войска Дагестанского отряда были разбросаны быстрым вторжением по Гумбету, Койсубу и Аварии; правые колонны его протянулись к Карате, для открытия сообщения с чеченским отрядом. Тем временем Шамиль ускакал с немногими приверженцами из Караты в Андалал. Два раза ограбленный на дороге, отброшенный в леса Караха людьми Кибит-Магомы, он успел, однако ж, добраться Гуниба. Присутствие имама на неприступном Гунибе, посреди Андалала, которого главные аулы еще не изъявили покорности, снова запутывало дело и требовало самых быстрых мер.

Сообщение между дагестанским и чеченским отрядами через Карату было открыто 27 июля. Через три дня потом в главный отряд прибыл генерал-адъютант барон Врангель. С обеих сторон путь в глубину гор был свободен. Главнокомандующий решился немедленно двинуть на Андадал все наличные силы, какими только мог располагать, чтобы подавить в этом крае приверженцев имама прежде, чем они успеют соединиться; тесно окружить Гуниб и запереть на нем безвыходно Шамиля с его последними мюридами. При виде развитых нами сил партия Кибит-Магомы должна была взять верх в Андалале; но все зависело от быстроты действий.

Главнокомандующий был уверен в спокойствии вновь покорившегося населения, которое не могло после такого крутого перелома снова перейти через несколько дней во враждебный стан. Полагаясь на энергию, если не на верность толпы, князь Барятинский двинул в Андалал все колонны, рассеянные по Аварии, Гумбету, Койсубу и Кара-Койсу, оставляя в только что завоеванных горах лишь несколько рот, для прикрытия мостов и складов провианта. Из чеченского отряда была направлена туда же колонна через Карату. Главное затруднение при этом непредвиденном сосредоточении войск в юго-западном углу гор состояло в их продовольствии. Заготовленные для похода провиантские склады дагестанских войск находились в Салатавии; на пределах Андалала ничего не было запасено. Немедленно были приняты чрезвычайные меры. Энергическое исполнение их начальником штаба Прикаспийского края князем Мирским позволило развить военную операцию со всею самостоятельностью, без малейшей потери времени; местными средствами, найденными в горах, черводарским транспортом, полковыми вьюками войска, собранные в Андалале, продовольствовались со дня на день через хребты Гумбета, Койсубу и Аварии; между тем как обозы, внезапно сформированные в покорном Дагестане, вывозили запасенный в горах провиант к ближайшим пунктам, откуда, после первых дней, андалальский отряд должен был уже правильно продовольствоваться.

Со вступлением значительных сил в Андалале враждебная Шамилю партия немедленно восторжествовала. Вся страна и окружающие ее горные общества изъявили покорность перед бароном Врангелем. Наши войска тесно обложили Шамиля, засевшего с несколькими стами отчаянных людей на недоступной вершине Гуниба.

Двинув генерал-адъютанта Врангеля в Андалал, главнокомандующий спустился 4 августа с чеченским отрядом в долину Технуцала и стал лагерем на Андийском-Койсу, около селения Конхидатль, против покинутых горских укреплений. На другой день в конхидатльский лагерь прибыл с кавалерией командующий войсками Лезгинской линии генерал князь Меликов.

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

Путешествие победителя Кавказа через покоренный им край имело вид торжественного шествия. Его встречали речами и адресами, салютационные залпы гремели в аулах, бесчисленные толпы стекались, чтобы взглянуть на него. Князь Барятинский проезжал Аварию, покорившуюся только две недели тому назад, не в голове войск, но как правитель, с одною конвойною сотнею; иногда даже его сопровождали исключительно туземцы. Горцы поняли, что теперь война действительно кончена.