Быстрые и жесткие нововведения Хаджи-Мухаммеда вызвали вначале глухой ропот со стороны князей и старшин, ни с кем не желавших делить власть, а затем появилась оформленная оппозиция во главе с Мамедом-Эдиге, которая обвинила Хаджи-Мухаммеда в незаконном присвоении власти и самоуправстве.
Эта оппозиция вошла в сношения с царскими властями и начала кампанию за изгнание Хаджи-Мухаммеда из Закубанского края.
Успехи Хаджи-Мухаммеда среди черкесов вызывали сильное беспокойство у царского военного командования, которое называло наиба «злонамеренным агентом», «возмутителем народного спокойствия».
Военный министр России А. И. Чернышев был встревожен тем, что власть «Гаджи-Магомета» над абадзехами все более расширяется, что он берет с населения штрафы и, накопив капитал, привлекает к себе горцев. Чернышев указывал, что император Николай I предписал найти людей из кабардинцев, которые взялись бы доставить «Гаджи-Магомета» живым за вознаграждение в тысячу червонцев.
17 мая 1844 года отряды Хаджи-Мухаммеда были вынуждены отступить в горы, где 19 мая, после шестинедельной болезни, их предводитель умер. При кончине Хаджи-Мухаммеда присутствовало много мулл, созванных им за несколько дней до смерти.
На смену ему по просьбе делегации от закубанских черкесов Шамиль послал в 1844 году другого своего наиба — муллу Сулеймана (старшего сына известного чеченского муллы Мустафы Абдулаева), хорошо знавшего Коран и мусульманское право — шариат. Царское военное командование высоко оценило Сулеймана-муллу, называя его в своих рапортах и донесениях «злонамеренным агентом» и «хитрым фанатиком». Адыги называли его «Сельман Эфенди».
Тайно пробравшись со своими соратниками через Кабарду в Адыгею, Сулейман Мустафинов сразу же приступил к делу. По прибытии его к горцам последние клятвенно обязались выслать ему войско. Среди шапсугов и натухайцев Сулейман сумел собрать отряд в несколько сот человек. Впоследствии, когда Сулейман перешел на реку Белую, отряд его увеличился до 2—3 тысяч человек, набранных от абадзехов и других племен, обитавших на северном склоне главного хребта.
Сулейман продолжил начинания Хаджи-Мухаммеда, укрепляя шариат и призывая к газавату. Проповедуя в аулах, Сулейман-мулла одновременно старался убедить адыгов оказать практическую военную помощь Шамилю. Сулейман Мустафинов имел специальное задание от Шамиля собрать военные отряды из адыгских мюридов и отправить их для соединения с войсками Имамата.
В 1845 году он сделал попытку «через земли Кабарды соединиться с Шамилем». В первые месяцы своего пребывания в Адыгее Сулейман-эфенди сумел подготовить почву для организации военной помощи Шамилю. Адагумское собрание решило, чтобы натухайцы (из аулов, расположенных на реке Псебебс, около Анапы и Новороссийска) выставили 30 конных всадников в армию Шамиля. Шапсуги же должны были выставить по 10 конных всадников с каждого большого ущелья и по 5 с малого ущелья. 2 мая 1845 года на племенном натухайском собрании в ущелье Ахог был разработан подробный план организации военной помощи Шамилю. Для руководства созданной военной группой были выделены особые лица.
Царское военное командование через своих лазутчиков было осведомлено о том, что Сулейман намеревается с «многочисленными толпами закубанцев пройти через Кабарду и Дигорию в Чечню». Для противодействия соединению отряда Сулеймана с войсками Имамата были собраны два крупных русских отряда у Прочного Окопа и у станицы Невинномысской. Царские войска преградили путь отряду Сулеймана, и адыгейцы не смогли пробиться через их заслоны и повернули обратно. Сам Сулейман-эфенди все же сумел пробраться к Шамилю.
Планы Шамиля о расширении фронта действий и перекрытии Военно-Грузинской дороги были прерваны широким вторжением армии Воронцова в горы Дагестана и Чечни в мае—июле 1845 года. В сентябре 1845 года, после своей грандиозной победы в Ичкерии, Шамиль посылает воззвание к улемам, шейхам, большим и малым хаджиям, кабардинской знати, абадзехам, темиргоевцам, мохошенцам и убыхам: «Вслед за посланным в благословенный край ваш... улемом Сулейман-Эфендием, я сам желал быть между вами, хотел, чтобы взаимные наши отношения сделать более близкими и твердыми; но вторжение в наши пределы множества нечистивых сил меня от того удержало».
В течение 1844—1845 годов к адыгам и Шамилю прибывали муллы, кадии, мастера пушечного дела из Малой Азии и Ближнего Востока, оказывавшие братскую помощь в борьбе с царскими оккупантами.
В начале 1846 года у шапсугов было собрание, на котором старшины, преданные Шамилю, постановили собрать значительный военный отряд для нападения на форты Лазаревский и Вельяминовский.
Шли слухи, что османский султан Абдул-Межид приказал своему флоту и всем сухопутным силам быть готовыми оказать помощь Шамилю. «От малого до великого все должны стоять перед своими врагами и до вспомоществования моего вам исполняйте безусловно его приказания» — говорилось в распространенном среди черкесов воззвании Ибрагима-паши Египетского (многие из подобных воззваний составлялись советником Шамиля Юсуфом-хаджи Сафаровым, долгое время жившим при дворе паши в Каире и Стамбуле).
Шамиль со своими единомышленниками вновь вернулся к плану совместных боевых действий и образования единого государства — Северокавказского эмирата (Дагестан и Черкесия). Советники имама настаивали на походе Шамиля на запад, говоря, что «черкесы — народ порядка, режима и дисциплины» и одного только появления имама в Кабарде будет достаточно, чтобы вызвать общее восстание всех народов от Каспия до Черного моря.
Момент действительно был самый удобный для западного похода. В апреле в Россию стал возвращаться 5-й пехотный корпус, стоявший на Кавказе с 1843 года. Об этом Шамиль знал подробно от разведки. Ежемесячно с настойчивыми просьбами о помощи имама Кабарде приезжали делегации кабардинских патриотов. Особенно настойчив был знатнейший уздень Малой Кабарды Мухаммед-Мирза Анзоров.
В апреле 1846 года по всему Кавказу начали носиться слухи о больших, небывалых по своим размерам, приготовлениях в горах. Слухи эти проникли за Кубань, до самой Черноморской береговой линии. По сведениям лазутчиков, житель дагестанского селения Аргуани (Салатавия) Салехиль-хаджи, взятый русскими в плен под Ахульго в 1839 году, затем бежавший из плена и скрывавшийся в Кабарде, ходил от имени кабардинцев к Шамилю с предложением поднять оружие против русских, если только Шамиль решится прийти к ним на помощь.
Шамиль вновь предпринял дальний поход, на сей раз в Кабарду. И в этом походе главной целью было объединение горских народов Кавказа в борьбе против колонизаторов. В апреле 1846 года, прорвав Сунженскую линию, Шамиль беспрепятственно вошел в Кабарду. «Кабардинская операция имама всеми военными авторитетами признается блестящей по замыслу и свидетельствует о недюжинных военных талантах Шамиля: удар был рассчитан на чувствительное место — на главный коммуникационный путь из России в Закавказье», — писал Н. Кровяков.
Осуществив беспримерный по масштабам и малочисленности потерь рейд по царским тылам, Шамиль вынужден был вернуть свои войска в Чечню. Во много раз превосходящие силы противника, отсутствие опыта длительных военных экспедиций, а также плохая скоординированность действий с закубанскими горцами и на этот раз не позволили достичь главной цели — объединения Кабарды с Имаматом.
В начале 1848 года царское командование, собравшее большие силы, провело серию истребительных военных операций против адыгов, в результате чего эти народы понесли большие потери. Колонизаторам удалось также спровоцировать среди народов Северо-Западного Кавказа междоусобные столкновения. В этот сложный, критический момент сюда прибывает один из мюридов Шамиля — Мухаммед, названный черкесами Мухаммедом-Амином («амин» по-арабски «верный»).
Мухаммед-Амин полностью оправдал свое назначение: храбрый воин, непреклонный борец за социальную справедливость, гибкий дипломат, красноречивый оратор, он со свежими силами и большой энергией принялся за внедрение шариата и проповедь газавата, которая нашла отклик во многих сердцах. Современники тех событий писали: «Народ, упавший духом, ожил, горя ненавистью и мщением к ним».
В 1849 году под руководством наиба Мухаммеда-Амина началось наступление отрядов закубанских народов. Царские войска несли большие потери. Более 10 лет наибу Шамиля Мухаммеду-Амину удалось вести войну на Северо-Западном Кавказе, отвлекая от Чечни и Дагестана большие силы царской армии.
Шок от поражения и опыт неудач заставил кавказского наместника Воронцова начать медленное завоевание Кавказа через закрепление за собой земель путем строительства на них поселений и вырубки лесов. Началось возведение укреплений в Малой Чечне и переселение станиц на основанную в 1842 году на реке Ассе и среднем течении Сунжи передовую чеченскую линию. Горское население этих земель истреблялось и изгонялось. Завоеванные на западе Чечни территории вместе с Ингушетией вошли в состав Военно-Осетинского округа (к концу войны граница этого округа дошла до реки Фортанги, западная часть Чечни оказалась под контролем образованного в 1845—1846 годах 1-го Сунженского полка). На месте уничтоженных чеченских селений одно за другим появлялись укрепления Бамут, Урус-Мартан, Воздвиженская (Чахкери) и другие.
