После поездки императора Николая Павловича на Кавказ наместник генерал Розен был смещен и на его место поставлен был генерал Головин. Разгром Ахульго, резиденции Шамиля, и его капитуляция произвели сильное впечатление на горцев. Они увидели, что русские войска способны проникать, казалось, в неприступные горные части Дагестана. Но деятельность русских войск сводилась лишь к экспедициям, к нанесению отдельных поражений мятежникам, разгрому пунктов их скопления, после чего войска отводились на свои базы. Мятежники получали передышку, снова собирались и снова начинали мятеж. Нанесенное Шамилю поражение принудило его согласиться на перемирие и выдачу в заложники своего сына, который был отправлен в Петербург.
Предоставленный самому себе, Шамиль по-прежнему продолжал свое дело. Он устроил новое Ахульго, перенес туда свою резиденцию и стал вновь привлекать к себе отпавшие от него области. Положение его облегчалось тем, что русские войска были отвлечены поднятым мятежом в кубанской области и Южном Дагестане. К 1839 году Шамиль собрал вокруг себя до 5 000 сторонников и стал вести нападения на сунжинскую линию и кумыкскую область. Все пути сообщения между Темир-хан-Шурою, Хунзаном и крепостью Внезапной оказались под угрозой его нападений и требовали охраны. Для сопровождения транспортов русскими было решено предпринять поход для ликвидации его нового укрепленного убежища. Для похода был собран отряд войск под начальством генерала Граббе.
Отряд встретился с частями мятежников на р. Аргуне, где их собрано было до 16 000 человек. После рукопашного боя Шамиль отступил в новый Ахульго. Граббе с войсками подошел к Ахульго и осадил его. Осада продолжалась десять недель, в результате чего русские войска оказались окруженными со всех сторон и попали в тяжелое положение. На помощь им подошли войска под начальством генерала Головина и совершенно изменили положение. Шамиль вступил в переговоры, требуя свободного пропуска, но получил отказ. Ахульго было взято, Шамиль бежал в Чечню.
Многие области Чечни подчинились Шамилю, чему благоприятствовали некоторые административные ошибки русских чиновников. Управлявший Чечней генерал Пулло сильно притеснял население, и чеченцы боялись, что русские превратят их в крепостных крестьян. К Шамилю была послана делегация с просьбой защиты их от русских. В 1840 году в Чечне был собран отряд в 10 батальонов при 16 орудиях и двух казачьих полках, команды милиции и линейных казаков под начальством генерала Голофеева. Перед наступлением русских все население Чечни ушло в дремучие леса за Сунжей и в «Черные горы». Чечня пустела. Шамиль оставил Чечню и отправился в горный Дагестан с целью поднятия горских народов. Он имел успех, и весь горский район признал его власть.
Объединив горный Дагестан, Шамиль овладел горными выходами на Прикаспийскую плоскость. Отсюда Шамиль имел целью занять Шамхальскую область и двинуться на Дербент, но был встречен русскими войсками и оттеснен в горы. В это время в районе Аварии появился Хаджи-Мурат, раньше состоявший на службе русских, имевший сильное влияние в стране. Он был обвинен по доносу правителя Аварии и, арестованный, отправлен под конвоем в Темир-хан-Шура, но по пути бежал и перешел на сторону Шамиля. Он стал поднимать население Аварии против русских, и правитель просил его помощи. Влияние Шамиля в горах возрастало, и генерал Головин в мае 1841 года решил предпринять сильную против него экспедицию.
Экспедиция имела лишь частичный успех. Шамиль переменил место деятельности, продолжал работу, и вскоре под влиянием Хаджи-Мурата в Аварии поднялось общее восстание. Шамиль укрепился в районе Гуниба. Влияние его распространялось, и начинались волнения среди осетин и черкесов. Против Чечни со стороны русских начали строиться укрепленные пункты, затруднявшие чеченцам нападение на станицы левого берега Сунжи. В 1841–1842 годах русские не имели значительных успехов, и Шамиль становился все более активным. Наместником Кавказа был назначен вместо Головина генерал Нейдгард. В Аварии умер подвластный русским властям шах Ахмет, и правительницей осталась его жена. Русский отряд в Аварии был под начальством генерала Клюге фон Клюгенау. Область Авария глубоко вдавалась в горный массив Дагестана и от обладания ею зависело спокойствие всего края.