В первое время Розен, не знавший тактики горцев, пытался навязать им крупное сражение, чтобы добиться решающей победы. Это только приводило к изнурительным маневрам большими формированиями войск, с приближением которых горцы рассеивались. Убедившись в бесполезности таких действий, Григорий Владимирович решил возобновить практиковавшуюся его предшественниками систему контроля территорий. Собрав в Дербенте отряд в три тысячи человек при 10 орудиях, он направил его в Табасарань, население которой активно поддерживало имама. Подавив сопротивление нескольких мелких групп и разрушив ряд аулов, отряд в течение сентября «навел порядок» в этом районе.
Затем он проследовал в шамхальство Тарковское, где назначенный имамом правитель Амалат-бек успел собрать до 10 тысяч воинов. Сражение произошло у аула Эрпели. В густом тумане русские скрытно подошли к противнику и после ружейно-артиллерийского залпа ударили в штыки. Мюриды не выдержали дружной атаки и обратились в бегство.
Дальнейшее продвижение отряда на юг заставило имама прекратить боевые действия в Дагестане и перенести их на территорию Чечни. Он организовал свою ставку в Чемкесенте, куда начал собирать силы.
Местонахождение вождя мятежников стало известно русскому командованию. Специально посланный отряд 1 декабря штурмом овладел Чемкесентом, рассеяв находившихся там горцев и потеряв 94 человека убитыми и 298 ранеными. Так, в целом безрезультатно для русской администрации завершился 1831 год, в течение которого в противоборстве с мюридами 673 военнослужащих были убиты, 2087 ранены и 116 пленены.
В следующем году Розен поручил генералу Вельяминову «навести порядок в Чечне». Выполняя этот приказ, в январе русские войска начали наступление со стороны Владикавказа на Грозный, следуя несколькими колоннами южнее Сунжи. Чеченцы, придерживаясь прежней тактики, без боя оставили селения и, укрывшись в лесах, перешли к партизанским действиям. Их результатом явилась потеря отрядами за две недели около 200 человек убитыми и ранеными без ощутимого ущерба для противника.
Официальный Петербург решил вмешаться в подготовку операций. От Розена потребовали все планы предварительно направлять в Военное министерство. Затем высшие военные чиновники, всячески избегавшие личной ответственности, переправляли эти планы на рассмотрение Паскевичу в Варшаву. Только после одобрения фельдмаршалом документы возвращались обратно на Кавказ в виде директив. Вполне понятно, что данный подход исключал всякую оперативность боевого управления на местах и порождал невиданную бюрократию, от которой и так всегда страдала армия. Подготовка очередной крупной операции на территории Чечни и Северного Дагестана заняла почти полгода.
В это время русский командующий предпринял попытку поссорить между собой ингушей и чеченцев. Первым, заявившим о своей преданности России, было официально разрешено совершать нападения на непокорные чеченские аулы, «дабы тем заставить сих последних более заботиться об охранении своего собственного имущества, и, следовательно, через то препятствовать им собираться большими партиями для грабежа в наших пределах». Замысел удался. 8 апреля отряд ингушей под командой прапорщика Берда Дударова напал на чеченский аул Торгам и угнал оттуда стадо из 200 баранов.
К концу июля подготовка операции была завершена и ее замысел одобрен в Петербурге непосредственно императором. В его основу была положена идея подрыва не только военного, но также экономического и морального потенциалов противника. По этому поводу в конце мая военный министр А.И. Чернышов писал Розену: «Начать действия против чеченцев лучше всего в конце июля или начале августа, когда жара не столько изнурительна и наступает время самого поспевания хлебов, дабы тем не дать им возможность собрать и скрыть свои запасы».
А для преследования непокорных чеченцев, скрывавшихся в лесах, рекомендовалось привлекать соседние горские народы, «предоставляя сим последним всю добычу, которую они приобрести могут». Такой подход «Его Величество считает и возможным, и полезным, ибо оно укоренит между ними вражду и помешает общему соединению против нас».
В начале августа 11-тысячный корпус двумя отрядами двинулся на территорию, контролируемую противником. Первый отряд, находившийся под командой Розена, из Владикавказа пошел в земли галгаевцев. Второй, возглавлявшийся генералом Вельяминовым, направился в районы, населенные карабулаками. Быстро и почти бескровно «приведя к покорности» эти народы, отряды соединились на реке Ассе и затем через неспокойные земли и аулы дошли до Герменчука. Там 24 августа состоялось сражение между русскими и мюридами, которое горцы проиграли. Герменчук был взят штурмом. Кизи-мулла и несколько тысяч уцелевших его сторонников ушли в горы. К тому моменту с начала экспедиции было уничтожено 60 чеченских селений, еще 80 аулов, изъявивших покорность и предоставивших заложников, были пощажены. Потери русских войск составили 68 человек убитыми и 427 ранеными.
После поражения под Герменчуком Кази-мулла ушел в родное селение Гимры, находившееся в ущелье реки Аварское Койсу и считавшееся неприступным. Но это не остановило командующего. Желая покончить с мюридами, он повел войска на штурм Гимр. 17 октября, сломив сопротивление горцев на подступах, русская пехота ворвалась в селение. Кази-мулла с 15 ближайшими сподвижниками укрылся в одной из башен. Но, видя безнадежность своего положения, с наступлением ночи он решил прорываться в горы.
— Если мы здесь останемся, — сказал он товарищам, — то вскоре, как собаки, околеем с голода. Аллах не простит нам такой позорной смерти. Попробуем же лучше пробиться сквозь ряды гяуров!
Горсть мюридов, надвинув на глаза папахи, обнажив шашки и кинжалы, с криком «алла» бросилась в последнюю атаку. Через несколько минут все они полегли в неравном бою. Среди убитых был и первый имам Дагестана Кази-мулла. Случайно уцелел всего один тяжело раненный, которого солдаты посчитали мертвым и великодушно оставили женщинам для захоронения. Им оказался Шамиль — будущий имам и многолетний враг России. При штурме Гимр 41 человек был убит и 339 ранены. Заслуги Розена в разгроме Кизи-муллы были отмечены золотой шпагой, украшенной алмазами.
Правда, гибель Кази-муллы вовсе не означала гибель мюридизма. Даже, наоборот, он получил новую идеологическую основу. Убиенный имам был вознесен в разряд святых, а борьба с «неверными» была объявлена главным делом для всех мусульман.
Вторым имамом Дагестана стал Гамзат-бек, один из ближайших соратников Казы-муллы.
Несколько удачных боев, проведенных мюридами под его командой, вызвали новый приток сторонников под зеленые знамена. Почти все ханства Нагорного Дагестана, кроме Аварского, были готовы объявить «газават» и включиться в войну с Россией. Но имам решил прежде всего укрепить свою власть в Аварии.
Это ханство было выбрано неспроста. По сведениям русской администрации в нем в 1833 году насчитывалось 25 тысяч жителей, разделенных на два лагеря во главе со своими ханами, формально лояльным к русскому правительству. При этом власть Сурхай-хана распространялась всего на три небольших аула, а остальные считались владением юного Нуцал-хана, реально не имевшего власти над ними. Вокруг же Аварии проживали воинственные лезгинские племена, враждебно относившиеся к России. Поэтому, захватив Аварию, Гамзат-бек мог легко превратить ее в плацдарм для борьбы с русскими на всем Северо-Восточном Кавказе.