Доклады Паскевича о продолжающихся беспорядках во вверенном ему крае в Петербурге вызывали соответствующую реакцию. Мнения о «мягких» мерах все чаще стали уступать под нажимом «силовиков». Постепенно на позицию последних встал и император. В конце сентября 1829 года он пишет Паскевичу: «Предстоит вам… усмирение навсегда горских народов или истребление непокорных. Дело сие не требует немедленного приближения, но решительного и зрелого исполнения… Я для сего представляю вам временно все войска, под командой вашей ныне находящиеся, с тем, чтобы удар был столь же решителен, как и внезапен. Прочее решать предоставляю вам».

В эти годы учение мюридизма только прокладывало дорогу в среду дагестанцев и чеченцев. Его «родителем» стал мулла Магомет, выходец из селения Яраг Кюринского ханства. Примерно в 1823 году, в одной из своих проповедей, он обратился к верующих со словами: «Народ! Вы не магометане, не христиане и не идолопоклонники. Магометане не могут быть под властью неверных… Кто считает себя мусульманином, для того первое дело — газават и потом исполнение шариата. Для мусульманина исполнение шариата без газавата не есть спасение. Будучи под властью неверных… все ваши намазы, все урючи, все странствования в Мекку, ваш нынешний брак и все ваши дети — незаконны…»

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

Случай подвернулся совсем неожиданно в лице Умалат-бея — племянника шамхала Тарковского и его зятя. Шамхал уличил племянника в связях с врагами и отобрал у него жену. Это считалось особым бесчестием среди горцев. Умалат-бей попытался примириться с тестем при посредничестве командира Куринского полка полковника Верховского, но когда переговоры сорвались, застрелил русского офицера и ушел в горы. Этот поступок приверженцами мюридизма были объявлены едва ли не началом газавата.

К тому времени в Дагестане появился еще один страстный поборник нового учения. Им стал Джемалэддин Гусейн казикумыхский. В 1824 году он был посвящен муллой Магометом в звание мюрида и начал активную пропагандистскую деятельность.

Но мюридизм не был известен в Чечне. Распространению его на эти земли «помог» также случай. О новом учении проведал известный в Чечне предводитель Бейбулат Таймазов. Этот человек, житель села Майртупа, слыл храбрым воином и пользовался большим уважением в народе. Он требовал такого же уважения к себе и от представителей русской администрации, которых он иногда посещал в крепости Грозной. Но, встретив холодный прием со стороны генерала Н.В. Грекова, затаил обиду. По витавшим слухам именно Бейбулат Тамазов пригласил в Чечню из Дагестана муллу, принесшего идеи мюридизма, и сам стал одним из ярых поборников нового учения.

Между тем обстановка в Дагестане и Чечне продолжала накаляться. Народ, возбуждаемый духовенством, готов был с оружием в руках выступить против «неверных». В горах появились турецкие агенты с оружием и деньгами. Быстро нашлись и местные вожди. Под их знамена начали собираться сотни горцев, готовых во имя Аллаха умереть в борьбе с «неверными».

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

6 мая того же года генерал Паскевич направил императору рапорт с изложением причин выступления горцев и предложением мер по их покорению. В нем он подробно останавливается на сильных сторонах противника. Одной из главных командующий считает многолетний опыт взаимоотношений горцев с русскими. «Уже более 50 лет, как они имеют дела с нами, и, к сожалению, были случаи, которые достаточны поселить в них мнение не в пользу нашу, — пишет Паскевич. — Одна мысль — лишиться дикой вольности и быть под властью русского коменданта, приводит их в отчаяние. С другой стороны, пятидесятилетняя борьба без успеха (со стороны русских) проникнуть в горные их убежища, дает им уверенность, что горы для нас недоступны. Обе сии причины достаточны побудить их к упорному сопротивлению. Нет сомнений, что мелкие владельцы скорее могут покорены быть видами личных своих выгод; но покорение вольных племен, ни от какой власти независимых, представляет более трудностей».

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

На будущее он предлагает два варианта действий. По первому предусматривалось одновременное стремительное наступление войск с нескольких направлений с целью вытеснения непокорных чеченцев в горы. Но при этом следовало учитывать, что «в сем случае неприятель, пользуясь ущельями, чащами лесов, горными протоками и другими местными препятствиями, противопоставит на каждом шагу оборону, хотя и недостаточную для удержания войск, но весьма способную утомить их. Горцы, не имея ни богатых селений, которые бы стоили того, чтобы защищать их, ни даже прочных жилищ, будут оставлять одно место за другим, угоняя свой скот вместе с семействами в отдаленнейшие горные ущелья. А по мере приближения к ним наших войск займут высоты либо разбредутся во все стороны; сами же, выжидая удобного случая, в местах закрытых не перестанут наносить вред войскам». Реализация данного способа требовала наличия большого количества войск, части из которых все еще находилась на границе с Персией и Турцией.

По второму варианту предлагалось одновременное медленное наступление с возведением укреплений на господствующих высотах, расположением в них гарнизонов и создание системы коммуникаций. Такой способ, по мнению командующего, был более надежен для достижения поставленной цели, но также требовал значительных воинских сил и продолжительного времени. Следовательно, ни один из вариантов в указанные сроки в полной мере реализован быть не мог.

Между тем, горцы перешли от слов к делу. 15 октября многотысячное скопище лезгин, скрытно спустившись с гор, внезапно напало на воинский отряд, занимавшийся прорубкой просек и прокладкой дорог в районе Старых Закатал. В скоротечном ожесточенном лесном бою русские потеряли 254 человека убитыми и 152 ранеными.

Разгневанный Паскевич приказал в качестве ответной меры стереть Старые Закаталы с лица земли. Но это было выполнено только через месяц после нападения и стало запоздалой ответной мерой, только обозлившей горцев. Антирусские выступления народов Северо-Восточного Кавказа грозило перерасти в настоящую войну. В определенной степени тому способствовал и отъезд в мае 1831 года Паскевича с Кавказа в Польшу, где вспыхнуло восстание против России. Граф Эриванский навсегда покинул Кавказ, потрясенный его победами, но не покоренный…