Царские власти решили положить конец деятельности шейха. Он был арестован и отправлен в Тифлис. Но, в очередной раз явив свою необыкновенную силу, шейх легко избавился от пут и укрылся в Табасаране. Вскоре затем он появился в Аварии, обеспечивая духовную поддержку ширящегося восстания.

В том же 1830 году в аварском ауле Унцукуль состоялся съезд представителей народов Дагестана. Ярагинский выступил с пламенной речью о необходимости совместной борьбы против завоевателей и их вассалов. По его предложению Магомед был избран имамом — верховным правителем Дагестана. К его имени теперь добавлялось «Гази» — воитель за веру. Шейх наставлял избранника: "Не будь поводырем слепых, но стань предводителем зрячих".

Принимая имамское звание, Гази-Магомед воззвал: "Душа горца соткана из веры и свободы. Такими уж создал нас Всевышний. Но нет веры под властью неверных. Вставайте же на священную войну, братья! Газават изменникам! Газават предателям! Газават всем, кто посягает на нашу свободу!"

Во время подготовки и проведения съезда в Унцукуле Шамиль, по обычаю, остановился в доме кунака своего отца — известного лекаря Абдул-Азиза. Осмотрев раны, полученные Шамилем в Хунзахском деле, лекарь нашел их не опасными, но требующими покоя и лечения. Шамиль вежливо отказался, ссылаясь на нехватку времени. Тогда Абдул-Азиз приготовил снадобья, которые могли бы хоть немного заменить более радикальные средства. Однако Шамиль забывал их пить, поглощенный более интересными делами. Но вскоре он стал замечать, что вместо кефира или бульона, подаваемого дочерью Абдул-Азиза другим гостям, в его чаше оказывались настои целебных трав. Он стал наблюдать за Патимат — дочерью лекаря, пытаясь понять, как ей удается сделать это незаметно для других. Он так и не раскрыл эту маленькую загадку, зато иное таинство — любовь — овладело им с неодолимой силой. Очарованный красавицей Патимат, он уже начал подумывать о более серьезном и долгом лечении в доме Абдул-Азиза. Почувствовав, что это сладкое наваждение способно серьезно помешать его бурной деятельности как ближайшего сподвижника имама, Шамиль решил не отказываться ни от одного, ни от другого. Выход был один — жениться. Родители Шамиля несказанно обрадовались, узнав о намерении сына. Они все еще надеялись, что семейная жизнь умерит в Шамиле пыл общественного переустройства. Денгав устроил пышную по горским меркам свадьбу, созвав на нее множество гостей. Но Шамиль и Гази-Магомед сумели и ее превратить в народный сход для пропаганды своих идей.

В апреле 1831 года Паскевич был срочно отозван с Кавказа и послан в Польшу заменить Дибича. Генерал успел отличиться на Балканах, получил к графскому титулу приставку «Забалканский» и в должности главнокомандующего подавлял польское восстание, но, не доведя дела до конца, умер от холеры.

Дибича настигла волна эпидемии, вспыхнувшей в «аракчеевских» военных поселениях и приведшей к "холерным бунтам". Уверенные, что смертельный мор наслан "их благородиями" докторами для истребления отслуживших свое солдат, поселяне убивали военных врачей, громили и жгли лазареты, поднимали бунты и ударялись в бега.

Печальную участь Дибича разделил и великий князь Константин, надеявшийся укрыться в Польше от беспокойной российской жизни, но не сумевший отгородиться от эпидемии.

Паскевич довершил успехи Дибича, взял Варшаву, навел повсюду жесткий порядок, сильно пошатнувшийся после либеральных экспериментов Александра I, получил титул светлейшего князя Варшавского и должность наместника Царства Польского. Восстание было разгромлено окончательно. Главари и зачинщики сурово наказаны, а их соратники сосланы в Сибирь и на Кавказ. Многие повстанцы бежали во Францию и Турцию, где образовали правительство в изгнании и употребляли все силы на организацию новых восстаний. Изгнанники сочувствовали освободительному движению горцев, часть из них, как и множество сосланных на Кавказ, оказалась позже в рядах армии горцев.

Вместо Паскевича командиром Отдельного Кавказского корпуса, главноуправляющим гражданской частью и пограничными делами был назначен барон генерал от инфантерии Григорий Розен.

Изучив положение дел на Кавказе, Розен счел идеи Паскевича о введении гражданского управления делом несбыточным и решил вернуться к управлению военному.

Административное деление тоже претерпело изменения: теперь край был разделен на две главные части: западную — под названием Грузино-Имеретинской губернии, и восточную — названную Каспийской областью.

При Розене были начаты широкомасштабные военные действия против отрядов имама по всему Дагестану.

Собрав сильный отряд мюридов, Гази-Магомед спустился на плоскость и построил укрепление в урочище Чумескент. Отсюда он призвал народы Дагестана объединиться для совместной борьбы за свободу и независимость. Главным его советником и военным командиром стал Шамиль. Первые стычки с регулярными царскими войсками принесли горцам первые победы. Гази-Магомед взял Параул резиденцию шамхала Тарковского. 25 мая 1831 года он осадил крепость Бурную. Но взрыв порохового погреба, унесший сотни жизней, и прибытие царских подкреплений вынудили Гази-Магомеда отступить.

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

Гази-Магомед тем временем атаковал укрепления на Кумыкской плоскости, поджигал нефтяные колодцы вокруг Грозной и рассылал эмиссаров, чтобы поднять на борьбу горцев Кабарды, Черкесии и Осетии.

В августе 1831 года Гази-Магомед совершил рейд на юг и осадил Дербент. На помощь дербентскому гарнизону двинулся генерал Коханов.

В ответ Гази-Магомед совершил стремительный переход через горы, прорвал Кавказскую пограничную линию и захватил крепость Кизляр. Среди прочих трофеев горцы увезли в горы много железа, которого им так не хватало для изготовления оружия.

Прорыв линии вызвал чрезвычайное неудовольствие Николая I.

Для решительного натиска на восставших было решено усилить Кавказский корпус частями, освободившимися после подавления восстания в Польше. Но привычная тактика не давала в горах желаемого результата. Значительно уступая отрядам Розена по численности, горцы превосходили их в маневренности и умении использовать местность. Поддерживало их и население. На помощь имаму прибывали все новые партии вооруженных горцев. В ряды восставших вставали не только простые горцы, бывшие рабы или крепостные, но и известные в народе люди.

Одним из первых поддержал имама Гамзат-бек Гоцатлинский, происходивший из рода аварских беков — чанка (рожденный от брака с женщиной простого происхождения). В первом походе на Хунзах Гамзат-бек был среди главных сподвижников Гази-Магомеда. Когда джаро-белоканцы, жившие за Кавказским хребтом, восстали и призвали на помощь имама, он направил к ним Гамзат-бека с отрядом мюридов. Гамзат-бек действовал весьма удачно и захватил четыре пушки. Ему удалось сдержать двигавшиеся с юга на Дагестан царские войска и даже угрожать царской администрации в Грузии. Но рано наступившая зима засыпала снегом горные перевалы и сделала невозможным его возвращение. Надеясь выиграть время, Гамзат-бек вступил в переговоры и явился в крепость Закатаны. Однако генерал Стрекалов задержал его под предлогом, что такие переговоры может вести лишь главнокомандующий, и отправил Гамзат-бека под усиленной охраной в Тифлис, где он и был арестован. Через несколько месяцев за пленного вступился Аслан-хан Казикумухский. Гамзат-бека отпустили, но оставили в заложниках его племянника. Хан с почестями принял Гамзат-бека, на которого имел свои виды. С его помощью он надеялся отомстить хунзахской ханше Баху-бике, которая оскорбила Аслан-хана, отдав обещанную его сыну дочь в дом шамхала Тарковского.