В следующем, 1839 году была предпринята широкая операция по всему фронту. На правом фланге десантный отряд генерала Раевского возвел ряд укреплений на Черноморском побережье. На левом фланге действовали Дагестанский отряд самого Головина и Чеченский — графа Граббе. 20 апреля отряд генерала Головина после упорного боя занял Аргуань (наши потери — 650 человек, горцев перебито до 2000). Затем оба отряда, соединившись, осадили 12 июня Ахульго — и 22 августа, пятым по счету кровопролитным штурмом, оплот Шамиля перешел в наши руки. У нас было 7000 бойцов при 17 орудиях. Горцев засело в Ахульго свыше 5000. Наиболее доступный склон горы, на который и была поведена атака, имел 50 саженей высоты при крутизне свыше 50 градусов. Штурмы 29 июня, 4 и 16 июля не удались (на этом последнем у нас убыло 875 человек, в том числе 52 офицера). Штурм 17 августа почти удался, но резервов не было, и наша потеря в этой четвертой безрезультатной попытке составила 557 человек. Наконец решительным приступом 22-го числа мы овладели этим орлиным гнездом. Горцев в этот день было убито свыше тысячи, в плен взято 900. Наш урон — 544 человека, а за всю осаду до 2500 человек. С горстью преданных мюридов Шамиль бежал в горы.
Дагестан казался усмиренным. Наружно все обстояло как будто хорошо, и ничто не предвещало той бури, что должна была разразиться с невероятной силой через несколько месяцев.
На 1840 год генерал Головин предполагал продвинуть правый фланг Кавказской линии на реку Лабу, а пространство между этой рекой и Верхней Кубанью заселить казаками. Но горцы предупредили этот маневр. В последних числах февраля вспыхнуло поголовное восстание всех лезгинских и черкесских племен. Скопища горцев овладели после отчаянной защиты фортом Лазаревом и укреплениями Николаевским, Вельяминовским и Михайловским. Михайловское укрепление занимало 400 тенгинцев и линейцев 5-го батальона под начальством штабс-капитана Лико. Горсть героев три дня отбивала 11 000 черкесов. Когда неизбежное совершилось и лавина горцев ворвалась в укрепление — рядовой Тенгинского полка Архип Осипов взорвал его на воздух с остатками гарнизона и победителями. Имя героя навсегда осталось в списках полка и вызывалось с тех пор на перекличке.
Шамиль поднял Чечню, где население было озлоблено сбором податей. 11 июля произошел жестокий бой у Валерика (воспет Лермонтовым). Шамиль, разбитый при Валерике генералом Фрейтагом, засел в горах — и туда к нему бежала вся Малая Чечня. Оттуда имам пытался пробраться в Северный Дагестан, но был отражен храбрым полковником Клюки фон Клюгенау с апшеронцами. Тогда Шамиль обратился на Аварию и осенью разгромил ее. Дерзкие набеги горцев до самого Терека продолжались до поздней зимы.
В Петербурге встревожились таким оборотом дел — и на Кавказ была двинута 14-я пехотная дивизия (из состава V корпуса). Весь 1841 год продолжались волнения в Аварии, правитель которой Хаджи-Мурат предался Шамилю. Операции в Чечне велись с переменным успехом. В 1842 году 20 февраля нами взят был аул Гергебиль. Шамиль пытался проникнуть в Южный Дагестан, но при Рычи путь ему преградил Ширванский полк. Князь Аргутинский-Долгорукий окончательно восстановил здесь порядок.
Однако пятидневный (с 30 мая по 4 июня) поход отряда Граббе — 10 000 человек при 24 орудиях и огромных обозах — на Дарго, резиденцию Шамиля в Чечне, закончился полной неудачей с потерей 60 офицеров, 1700 нижних чинов и 1 орудия. Горная местность совершенно не благоприятствовала действиям крупных масс войск и их обозов. Дела пошли совсем скверно, и в августе заволновались и те племена, что до сих пор оставались в стороне от движения. Зимой с 1842 на 1843 год горцы предпринимали набеги до Кизляра и даже до Ставрополя. В результате всех этих неудач генерал Головин был заменен генералом Нейдгардтом. Дух в Петербурге сильно упал, и военный министр князь Чернышев исходатайствовал высочайшее повеление в 1843 году экспедиций не производить. Однако горцы стали настолько дерзки, что генерал Нейдгардт вынужден был уже весной предпринять ряд экспедиций.
В конце августа Шамиль нанес ряд поражений нашим отрядам в Чечне и овладел несколькими укреплениями (с 27 августа по 21 сентября мы лишились 55 офицеров, 1562 нижних чинов из общего числа 6000 и потеряли 12 орудий). Поздней осенью этого тяжелого 1843 года нас ждал второй удар. 3 ноября Шамиль овладел Гергебилем, где горсть храбрецов повторила подвиг Архипа Осипова в Михайловском укреплении. Гергебиль занимало 3 роты (350 человек Тифлисского полка, державшихся десять дней против 10 000 неприятелей). Укрепление взорвали юнкер Чаевский, унтер-офицер Неверов и рядовой Семенов. Связь между Северным и Южным Дагестаном была нарушена. Весь Восточный Кавказ вспыхнул как порох.