4 февраля 1830 года во главе около 3000 человек Кази-Мулла двинулся на Анди, где к нему присоединилось еще столько же людей, хотя сначала население этой страны, опасаясь сворачивания торговых отношений с русскими (они торговали бурками) и чеченцами, жившими внутри русских оборонительных линий, не выказывали особого желания присоединяться к движению против хана Аварии.

По пути Казн столкнулся с вооруженной оппозицией со стороны жителей соседних аулов Ирганай и Касатлы, однако легко победил их, потеряв только 27 человек убитыми и ранеными, после чего отослал 60 заложников в Гимры и Унцукуль, где их тоже посадили в ямы.

История похода в Аварию в полном объеме демонстрирует его невежество и фанатизм, при этом показательна одна деталь, если рассматривать ее в связи с предполагаемым еврейским происхождением этого народа. Он прошел весь путь от Гимр пешком, поскольку еще не поднял знамя газавата, и держал себя столь приниженно, что считал грехом ехать верхом. Время от времени он останавливался, наклонялся вперед, приложив руку к уху, как будто прислушиваясь к чему-то, хотя в горах царила тишина. Когда его последователи спросили, что он делает, он ответил: «Разве вы не слышите? Я слышу бряцание цепей, в которых ко мне ведут русских пленников!» Затем, сев на камень, он стал излагать свои идеи и строить планы о будущей славе ислама. «Когда мы изгоним гяуров с Кавказа и возьмем Москву, мы пойдем в Стамбул, и если увидим, что султан – религиозный человек, строго следующий нормам шариата, то не тронем его и пальцем; если же нет – горе ему, мы закуем его в цепи, а его империя перейдет в руки верных сынов ислама». Когда он приблизился к Анди, ему навстречу вышли все жители, и «многие срывали и разбрасывали вокруг себя одежды». Вероятно, если бы поблизости были деревья, то «другие» срубили бы «ветки с деревьев и устлали бы ими путь».

Этот эпизод произвел необыкновенное впечатление на население многих регионов Кавказа. В самой Аварии большая часть населения приняла ислам, но столица Хунзах, город, в котором было более 700 домов, была в основном заселена беженцами из разных районов Кавказа. Большей частью это были разбойники, не желающие подчиняться суровым законам мюридизма. Построенный на высоте 1690 метров над уровнем моря, откуда идет спуск к Авар-Койсу, Хунзах имел сильные укрепления и оборонительные башни, и Паху-Бехи, предположив, что может рассчитывать на верность жителей, решила бросить вызов Кази-Мулле и защищать столицу до конца. 14 февраля 1830 года мюриды пошли в атаку двумя отрядами, которыми командовали сам имам и Шамиль. Они шли в бой с криками «Бог велик, нет другого Бога, кроме Аллаха». Разбойники Хунзаха никогда не видели и не слышали ничего подобного; у них в буквальном смысле опустились руки, и беспорядочный огонь, который они вели, вдруг стих. В этот момент, словно видение, перед ними появилась фигура Паху-Бехи. Она была ужасна в своем гневе, с мечом в руке, с пылающими щеками и горящими глазами. «Авары, – воскликнула она, когда все обратили на нее свои взоры, – вы недостойны носить оружие. Если вы боитесь, отдайте свое оружие нам, женщинам, а сами спрячьтесь за нашими юбками!» Задетые этим горьким укором, защитники вновь взялись за оружие как раз тогда, когда враг был готов влезть на крепостные стены, и отбросили его назад. Увидев это, те авары, которые присоединились к мюридам, отделились от них, и последние обратились в бегство, оставив на поле боя 200 человек убитыми, много раненых и 60 пленных в руках торжествующей ханши. Над Шамилем нависла опасность быть убитым своими потерявшими разум последователями, но его спасло вмешательство дервиша, первого из многих едва избежавших смерти. Этот факт был важен для суеверных горцев, которые посчитали его избранным Аллахом для работы на земле. Хаджи-Мурат, как его впоследствии нарекли, собрал все знамена и штандарты, оставленные мюридами на поле боя, и отослал их в Тифлис, как доказательство верности Аварии России, а Кази-Мулла в смятении вернулся в Гимры, заявив, что это поражение было наказанием свыше за отсутствие веры у людей и их аморальность.

Он намеревался, взяв Хунзах, завоевать ту часть Чечни, которая называлась Аух, и атаковать русских в их крепости Внезапной. Зная это, русский командир барон Розен поспешно направился на защиту того места с небольшим, но мобильным отрядом. Услышав о событиях в Хунзахе, Розен поспешил на гору Харахс и там принял присягу на верность от жителей всех деревень района Койзубу, за исключением Гимры. Удовлетворившись этим, он отошел вместе со своим отрядом, чем и воспользовался Кази-Мулла, чтобы убедить своих павших духом сподвижников в том, что русские не посмели атаковать его. Через несколько недель он снова был во главе крупного отряда в Агач-Кале («Деревянная башня»), или Чумкешкенте, как его еще называли. Это было абсолютно неприступное место в покрытых густым лесом горах к югу от Эрпели. Русские под командованием генерал-майора князя Бековича попытались выбить его оттуда, но безуспешно. Овеянные еще большей славой крупного войска, они двинулись на Атли-Буйюн, деревню между Петровском и дорогой на Шуру, одержали там победы еще над одним русским командиром, бароном Таубе, затем разрушили Параул, резиденцию шамхала, взяли Тарку и осадили и чуть не взяли русскую крепость Бурную. Однако, поскольку подкрепление подоспело в решающий момент, Кази-Мулла был разбит и понес тяжелые потери. Вынужденный отступить, он вновь занял позицию в Чумкешкенте. Это было в конце мая 1831 года, а через 10 дней он двинулся на Внезапную и осадил ее. Русская армия под командованием генерала Эммануэля поспешила на выручку крепости, и имам, наученный горьким опытом осады Бурной, вовремя отошел в соседние леса. Когда русские стали преследовать его, он нанес им сокрушительное поражение, захватив одну пушку и ранив самого Эммануэля, в результате чего тот передал командование в руки Вельяминова[83].

На другой стороне гор Хамзад, впоследствии – второй имам, сумел поднять восстание среди джаро-белоканов, и во время его подавления русские под командованием генерала Стрекалова потерпели жестокое поражение при Закаталах, потеряв 6 офицеров и 243 рядовых убитыми, 10 офицеров и 139 рядовых ранеными. Было потеряно также 4 пушки, и, к большому разочарованию Паскевича и императора Николая, оба батальона Эриванского полка струсили и бежали с поля боя.

Кази-Мулла вновь отошел в Чумкешкенту, где в августе принял представителей Табасарана, которые предложили ему повести их на священную войну против русских. Он, не теряя ни минуты, отправился в Дербент, который из-за ложного слуха о войне с Персией остался под охраной всего лишь двух батальонов. Кази-Мулла держал этот город в осаде в течение 8 дней (с 12 по 20 августа), однако неделю спустя Паскевич сообщил Нессельроде об успешном снятии осады. И все же 1 ноября Кази-Мулла совершил смелый и успешный поход на Кизляр в нижнем течении Терека. Этот город был знаком и ему, и Шамилю по визитам к знаменитым муллам, когда они еще изучали теологию. Город был взят и разграблен, а Кази-Мулла вернулся в Дагестан с 300 пленными, в основном женщинами, и с добром общей стоимостью в 4 млн рублей (хотя, пожалуй, это явное преувеличение). Противопоставить этому успеху русские могли только штурм Эрпели. Командовал этой операцией генерал Панкратьев. Генерал Каханов решил во что бы то ни стало уничтожить Чумкешкент. После неудачной атаки 26 ноября генерал Миклашевский повел свои войска на очередной штурм этой крепости 1 декабря. Несмотря на все препятствия, крепость была взята. Как писал декабрист Бестужев, «операция стоила нам 400 жизней, хотя надо было взять всего лишь деревянную башню, которую защищали не более 200 человек. Русские творили чудеса храбрости. 8 наших лучших офицеров пали, включая самого Миклашевского». Он добавляет, что бой при Чиркее, который состоялся немного позже, закончился более счастливо, «поскольку мы вернули себе пушку, захваченную у Эммануэля, но это стоило нам 80 человек». Генерал Панкратьев в отчете о взятии Агач-Калы пишет, что «благодаря решимости и злости наших войск ни один вражеский солдат не был взят в плен».