К концу 1836 года Шамиль подчинил своей власти весь горный Дагестан. Оставалось лишь решить старую проблему — покорить Хунзах, столицу Аварского ханства. Правитель Аварии, искушенный в горских делах, настойчиво требовал от царского командования пресечь деятельность Шамиля, пока это еще было возможно.
Клюгенау долго колебался, не желая нарушать сложившееся в Дагестане относительное спокойствие. Но тревога командующего Кавказским корпусом барона Розена относительно усиливающегося в горах влияния Шамиля, которого он называл «хитрым возмутителем», заставила военно-окружного начальника в Дагестане генерала И. Реутта трезво взглянуть на реальное положение вещей.
В Дагестане и Чечне было спешно организовано несколько экспедиций с целью уничтожить влияние Шамиля и окончательно усмирить край.
Реутт добрался до Хунзаха, не встретив сопротивления, и вернулся в Темир-Хан-Шуру ни с чем. Горцы расценили это как победу Шамиля.
Генерал Пулло, в безуспешной погоне за Ташов-Гаджи, после тяжелого боя занял Зандак и установил в округе свою власть. Но как только его отряд ушел обратно, новая власть исчезла вместе с ним.
Результат всех этих предприятий оказался прямо противоположным их целям. Авторитет и власть Шамиля только усилились, набеги на линии участились, восстания охватывали прежде спокойные области, а армия имама быстро увеличивалась.
Наряду с военными мерами Розен предпринимал усилия и для морального противодействия Шамилю. Его пламенным призывам, увлекавшим целые общества, было решено противопоставить проповеди ученого муфтия из Казани Т. Мустафина.
В инструкции, данной Мустафину при отправлении его в Дагестан «для убеждения горцев в неправильном толковании шариата мюридами и расположении их в пользу царизма», Розен обрисовал ему свое понимание истории Кавказа, объяснил разделение Дагестана и положение главных его лиц. Особое внимание муфтия было обращено на деятельность имамов, представленных разбойниками и изуверами, которые «вводили легковерный народ в заблуждение под видом сохранения буйной независимости и домогались лишь личных выгод».
Несмотря на столь серьезную подготовку, миссия успеха не имела, так как простых горцев больше интересовали не тонкости шариата, а неотделимые от него свобода и независимость.
Ввиду того что дела в Дагестане принимали все более опасный оборот, в мае 1837 года была организована новая, более сильная, «Аварская» экспедиция под командованием генерала К. Фезе. Фезе тоже был горцем, только швейцарским. Наемником участвовал в Наполеоновских войнах, затем поступил на русскую службу. В Польской кампании 1831 года он уже командовал бригадой гренадеров, а теперь, на Кавказе, пехотной дивизией. Фезе предписывалось решительно покончить с мятежниками, разорить столицу Имамата Ашильту и окончательно утвердиться в Аварии.
Отряд, насчитывающий более 5000 человек, с пушками и мортирами, двинулся к Хунзаху. По пути Фезе исправлял дороги и строил укрепления. В Хунзахе выяснилось, что Шамиль с отрядом мюридов находится в Телетле, южнее Хунзаха, тогда как Ашильта находилась севернее. И что имама уже осадила милиция местных ханов. Послав им на помощь часть своих войск, Фезе решил сначала покончить с Ашильтой.
«Мы заключили мир…»
Столица Имамата, укрытая в недрах дагестанских гор, встретила Фезе в полной боевой готовности. В искусно укрепленных каменных саклях засели мюриды. Их было немного, но это были воины, знавшие толк в битвах.
Фезе пустил в ход артиллерию, затем бросил на штурм аула войска. Жестокая схватка длилась с утра до заката солнца. Но, заняв наконец Ашильту, Фезе увидел себя почти полностью окруженным толпами повстанцев, пришедших на помощь ашильтинцам. Под угрозой полного разгрома Фезе не решился вернуться в Хунзах и, неся большие потери, спешно отступил к Темир-Хан-Шуре. Пополнив отряд свежими частями, упрямый Фезе вновь двинулся на Хунзах, а затем — к Телетлю, надеясь покончить с блокированным там Шамилем.
Его надежды увидеть Шамиля уже плененным не оправдались. Вдохновляемые личным примером имама и предводителем телетлинцев Кебед-Магомой, ставшим позже ближайшим сподвижником Шамиля, защитники аула стойко отражали атаки и совершали дерзкие вылазки. Осада Телетля, безуспешно длившаяся более месяца, грозила обернуться катастрофой наподобие ашильтинской и полным крахом экспедиции.