В мае 1831 года Паскевич был срочно вызван в Польшу и покинул Кавказ. Его в общем кратковременная деятельность свелась лишь к двум войнам, зато блестяще проведенным, с внешним врагом. Внутри края его администрация не успела пустить корни. На его место главнокомандующим был назначен генерал барон Розен 1-й.
Утвердившись в урочище Чумкесент у Темир-Хан-Шуры, Кази-мулла стал скликать горцев на священную войну с гяурами. Полчища мюридов разгромили Кизляр и обрушились на Бурную и Внезапную, но были отбиты. Генералы Панкратьев и Вельяминов усмирили большую часть мятежников и 1 декабря 1831 года овладели Чумкесентом. Кази-мулла бежал в Гимры - совершенно неприступное горное гнездо, где снова стал собирать ополчение. Русские смогут сойти в Гимры только дождем, - говорил он.
И русские сошли в Гимры дождем! Чтоб положить конец восстанию, барон Розен собрал летом 1832 года до 10000 при 16 орудиях, двинулся на Гимры и 17 октября овладел ими жестоким штурмом. Скопища горцев были рассеяны, а сам Кази-мулла был убит. В походе на Гимры принимали участие Эриванский карабинерный полк и батальоны полков Херсонского гренадерского. Тифлисского, Московского, Бутырского пехотных и 41-го егерского (Мингрельского). Мы лишились 41 убитыми и 339 ранеными. Кази-мулла с 15 самыми отчаянными мюридами (среди которых был Шамиль) засел в одной из башен. Если мы здесь останемся, - сказал он своим товарищам, - то как собаки околеем с голода. Аллах не простит нам такой позорной смерти. Попробуем же лучше пробиться сквозь ряды гяуров! Надвинув папахи на глаза, горцы ринулись в шашки и все до одного легли после отчаянной сечи. Шамиль, проколотый штыком насквозь, был оставлен замертво. Пронзенное русскими штыками тело Кази-муллы сделалось предметом поклонения.
Движению, казалось, был нанесен окончательный удар. По крайней мере, так полагало и в этом смысле отписало в Петербург русское начальство. Наши силы на Кавказе были поэтому сокращены и, по проведении военной реформы 1833 года, находившиеся, там войска новообразованного VI корпуса отозваны в Россию. В Кавказском корпусе остались 19-я, 20-я, 21-я пехотные дивизии. Гренадерская бригада, нижегородские драгуны (10-й эскадрон), 37 линейных батальонов и казачьи войска.
Преемником Кази-муллы объявил себя Гамзат-бек. Он вновь собрал мюридов и решил пока не трогать русских, а предварительно овладеть Аварией. Это удалось ему в 1834 году, после чего Гамзат решил покорить Дагестан. Однако он был убит одним фанатиком аварцем. Движение возглавил другой сподвижник Кази-муллы Шамиль.
Подчинение аварского ханства мюридами встревожило наше правительство, и Розену поведено было ввести войска в Аварию, что и было им исполнено. Все 1835 и 1836 годы прошли в бесполезных переговорах с горцами. Шамиль, принявший титул имама, упрочивал тем временем свою власть над дагестанскими племенами. Главный свой оплот он устроил на почти отвесной скале близ слияния Андийского и Аварского Койсу, названной им Ахульго, что по-арабски значит прибежище. Влияние его возрастало с каждым днем.
* * *
1837 год ознаменовался двумя событиями. В мае месяце барон Розен предписал генералу Фези{103} предпринять экспедицию на Ахульго. Фези овладел аулами Тилитль, Ашильдой и всем ахульгинским районом. Однако недостаток продовольствия и угроза сообщениям побудили его очистить занятый район. Вся эта экспедиция принесла нам в общем больше вреда, чем пользы, ибо Шамиль (хоть и выразивший на словах покорность) стал теперь убеждать горцев, что Аллах ему сопутствует и русские не в состоянии с ним что-либо поделать. Будь в то время на Кавказе сколько-нибудь проницательные военачальники, опыт этой экспедиции пошел бы им впрок и армия была бы набавлена в дальнейшем от многих безрезультатных, а то и прямо неудачных походов.
В сентябре Кавказ посетил Император Николай Павлович. Государь остался недоволен общим состоянием края, брожением умов в Дагестане, разбоем в татарских ханствах и отсутствием связи между укреплениями на Сунже. Розен был смещен, и на его место назначен генерал Головин. Новый главнокомандующий обратил свое внимание сперва на правый фланг Кавказской линии - Черноморское побережье и Закубанье, где основаны укрепления Новотроицкое и Михайловское. В 1838 году основан Новороссийск, проведена Военно-Грузинская дорога из Тифлиса через Кавказский хребет на Владикавказ, и этот последний соединен с Моздоком линией кордонов.