Еще после гибели Кази-Муллы граф Розен посчитал дело в основном выигранным и переключился на Северо-Западный Кавказ, где воевали черкесы. По договору 1829 года турецкий султан «передал» их под власть русского царя. Как рассказывают, черкесский вождь, узнав об этом, указал русскому генералу на птичку и сказал: «Генерал, дарю тебе эту птичку, возьми ее!» Тем не менее сопротивление здесь шло не так интенсивно, и императорские войска постепенно пресекли укрепленными линиями набеги противника вглубь российской территории. Но именно в это время Гамзатбек, а затем Шамиль вновь собирали Чечню и Дагестан под зеленые знамена.
Самые дальновидные из русских командиров предвидели, сколько бед в будущем это принесет. Вот что пишет в эти годы контр-адмирал Лазарь Серебряков: «С каждым годом бездействие наше удаляет достижение цели; горцы приобретают более и более смелости, опытности, единодушия. Прежде племена их вечно обуревались междоусобиями; но с появлением нашим у них возникли дух народности, небывалое согласие, понятие общих усилий; война с нами прекратила их раздоры, союз их с каждым днем становится все теснее, и если не предупредим их покорением, то нельзя ручаться, чтобы не появился, наконец, между ними человек с диким гением и сильным характером, который воспламенит в сердцах азиатцев всегда тлеющие страсти фанатические. И, став в челе народа, вступит с нами за его разбойничью независимость в борьбу правильную, упорную и кровопролитную».
Так и получилось. Правда, в 1837 году россияне разгромили Шамиля, и появилась даже надежда, что он официально присягнет Николаю I. Но переговоры сорвались. Оказалось, что имам в своей горской манере лукавил — в самый последний момент он отказался ехать в Тифлис, заявив: я нисколько не уверен, что меня там не схватят.
Пришлось генералу Евгению Головину, сменившему Розена, продолжать строить крепости — уже от устья Кубани до самой Мингрелии. Только в 1839-м он решился наступать по двум направлениям на Северо-Восточный Кавказ. Шамиль два месяца сидел в осаде в Ахульго, отдал своего первенца Джемал-Эддина заложником для начала переговоров, но сам так и не сдался. Аул был взят штурмом, а имаму лишь с несколькими приближенными удалось прорваться и уйти.
Казалось, мюридизм побежден. Но генерал Пулло, подчиненный Головина, начал грабить и разоружать местное население, в результате чего Шамиль за считанные дни возвратил себе власть. Русские начали терпеть поражения. В кампании 1842 года армия потеряла 1500 солдат и офицеров — очень много для Кавказской войны. А имам в следующие несколько лет на глазах у удивленных современников овладел всем Дагестаном и большей частью Чечни, уничтожил множество укреплений — плоды упорных трудов русских солдат — вместе с их гарнизонами. За 1843 год имамат расширился больше, чем вдвое. Даже знаменитый Хаджи-Мурат, покинув русский стан, стал Шамилевым наибом (наместником) Аварии. Тем временем черкесы разорили и срыли четыре укрепления Черноморской береговой линии. С моря им всячески помогали турки и англичане, одновременно с этим ведя активную критику политики России на Черноморском побережье.
