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