В конце ноября 1836 года Шамиль направил русскому командованию предложения о перемирии, носившие характер ультиматума. В этом документе говорилось: «Уведомляю вас, что войска Кайсубулинского, Гумбетовского, Андалялского, Боголалского, Чамалалского и других обществ единодушно признают и принимают мусульманскую веру, беря на себя ее законы. Все они заключат перемирие или будут вести борьбу совместно. Они разорят аулы, которые вздумают уклониться от общего согласия. Поэтому вам нет никакой пользы вести переговоры с жителями одного или двух аулов. Если вы намерены помириться с нами, на что и мы согласны, то заключайте общий мир со всеми без обмана и коварства. Если же вы хотите сражаться, то знайте, что мы мужчины, которые не отказываются от войны. Между нами и вами было перемирие, которое вы нарушили неоднократным вторжением в нашу сторону, без всякой причины со стороны нашей. Поэтому виноваты вы, а не мы».
Так закончился первый, относительно мирный, период власти Шамиля на Северо-Восточном Кавказе. Розен также постарался использовать относительное затишье для закрепления русских войск в ранее занятых районах Северного Кавказа. Там возводились укрепления, между которыми прорубались просеки, расчищались дороги, устраивались мосты. Правда, все эти инженерные работы производились в ходе постоянных стычек с горцами и приводили к значительным потерям среди войск. За период с 1834 по 1836 год в ходе экспедиций было убито 558, ранено 1782 и пленено 353 российских военнослужащих.
В 1837 году русское командование решило покончить с мюридизмом среди народов Северо-Восточного Кавказа. Однако когда Розен начал собирать для этого силы, то оказалось, что из 85-тысячного Кавказского корпуса для действий в Чечне и Дагестане удастся выделить всего восемь тысяч человек. Командование этим соединением было поручено генерал-майору К.К. Фези.
В конце января экспедиционный отряд из Грозной направился в Западную Чечню. Углубившись в леса, он уничтожил несколько аулов, не встречая сильного сопротивления горцев. Но затем, лишь немного ослабив бдительность, войска подверглись ряду внезапных ударов больших скопищ чеченцев. Не добившись значительных результатов, потеряв убитыми и ранеными почти 650 человек, Фези был вынужден в конце марта вернуться в Грозную.
В начале мая этот генерал во главе 6-тысячного соединения из Темир-Хан-Шуры направился в Аварию. Пройдя за 22 дня 150 верст по горам, 29 мая русские заняли Хунзах.
В это время Шамиль с основными силами находился в аулу Ахульго. Фези направил туда авангард, но имама в ауле не оказалось. С большим отрядом мюридов он заблаговременно перебрался в селение Телетль, где приготовился к обороне. Правда, она была построена так неумело, что русским войскам удалось окружить противника.
Положение имама и его отряда было критическим. Поняв это, Шамиль пошел на хитрость. Через парламентера он согласился прекратить борьбу и присягнуть на верность России.
Обрадованный Фези поверил коварному горцу. Приняв письменную присягу через посла и взяв десяток заложников, в том числе старшего сына имама, он снял осаду Телетля и возвратился в Хунзах. Так была упущена реальная возможность покончить с мюридизмом на Северном Кавказе. Одержанная «победа» обошлась России потерей 229 человек убитыми и 724 ранеными.
Шамиль не собирался выполнять данного обещания. Более того, он пересмотрел свои планы и решил объединить усилия всех мусульманских народов Северного Кавказа прежде, чем начинать новый этап борьбы с Россией. При этом главный расчет делался на чеченцев, по своим врожденным и воспитанным качествам наиболее отвечавшим требованиям бескомпромиссной религиозной войны. К тому времени они стали основными носителями идей мюридизма, главной военной силой имама.
Осенью 1837 года Кавказ впервые посетил император Николай I. Желая показать всему миру, что Россия твердо стоит на этих землях, он объехал почти все Закавказье в сопровождении конвоя, состоявшего исключительно из горцев: грузин, кабардинцев и армян. В память о визите высокого гостя все члены конвоя и местная администрация, встречавшая государя, были награждены специально изготовленными по этому случаю серебряными медалями с надписью «Кавказ — 1837 год». В целом же Николай I остался доволен положением дел в крае и войсках Кавказского корпуса, но был крайне возмущен состоянием отдельных частей и моральным обликом некоторых офицеров. В борьбе с недостатками он действовал со свойственной ему жесткостью. Так, на смотре войск, состоявшимся 11 октября, император публично лишил флигель-адъютантского звания и отдал под суд зятя командующего командира Эриванского карабинерного полка князя Александра Дадиани. Суд подтвердил вину офицера, он был лишен чинов, орденов, княжества и сослан в Вятку, где и провел последующие 16 лет.
Розен тяжело переживал случившееся. Сославшись на состояние здоровья, он попросился в отставку, а получив ее, был назначен присутствующим в московские департаменты Сената. Преклонный возраст генерала и размеренная жизнь Первопрестольной способствовала размышлениям о прожитом и пережитом, в котором Кавказ занимал особое место. Под давлением мыслей в 1839 году Владимир Григорьевич подал императору всеподданнейшую записку о состоянии Кавказского края и военных действиях против горцев. Из нее следовало, главный противник России — горные народы Северного Кавказа, на конец 30-х годов русской стороной изучены были весьма мало, а власть России на Кавказе крайне слаба. При этом, признавая, что за время правления краем ему не удалось решить главной проблемы края, в качестве таковой он выдвигал более решительное покорение горцев с привлечением военной силы. Розен писал: «В таком точно виде представился мне Кавказский край в 1831 году, когда я по Высочайшему Вашего Императорского Величества повелению принял начальство над оным, и чем более вникаю в разные отрасли управления, чем более знакомлюсь с нравами, обычаями и образом мыслей разноплеменных народов здесь обитающих, тем более удостоверяюсь в необходимости иметь в виду при управлении Кавказом одну общую цель, которая в военном отношении должна клониться первоначально к покорению горцев, а потом к совершенному успокоению всего края».
Свою сдержанность в применении силы он объяснял тем, что имел инструкции, еще ранее направленные И.Ф. Паскевичу, которые «клонились единственно к сохранению спокойствия во Всемилостивейше вверенном мне крае и к временному усмирению племен, более других обнаруживших неприязнь и недоброжелательство свое к нам». Столь мягкая политика, по мнению бывшего командующего, расценивалась горцами, как слабость России, позволявшая им игнорировать требования ее правительства и местной администрации. Анализа же самих проведенных операций и боев записка не содержала, что свидетельствует о фактическом отсутствии теоретической базы военного искусства действий в горах в тот период.
В.Г. Розен умер 6 августа 1841 года в Москве и был похоронен в Даниловом монастыре.
Очередным наместником Кавказа стал 56-летний генерал-лейтенант Е. А. Головин. Евгений Александрович происходил из старинного боярского рода, представители которого являлись ближайшими сподвижниками Петра I. Он окончил Московский университет, после чего в 1797 году поступил на военную службу. Активно участвовал в войнах, которые вела Россия в начале XIX века, из заграничного похода вернулся в 1814 году в чине генерал-майора, кавалером многих орденов, в том числе и ордена Св. Георгия 4-й степени. За распорядительность при усмирении восстания декабристов Головин был пожалован генерал-адъютантом. В 1828–1829 гг. сражался с турками на Дунае и за боевые отличия был награжден орденом Св. Анны 1-й степени с императорской короной и золотой шпагой, украшенной алмазами.