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