В 1851 году Шамиль послал Хаджи-Мурата в прибрежные районы Кайтаго и Табасаран, чтобы поднять их жителей на восстание против русских. И снова он отметился отчаянной и рискованной экспедицией, одной из тех, которые навечно вписали его имя в историю Кавказской войны. С 500 всадниками он ночью вошел в Буйнах, богатый аул на военной дороге, соединяющей Дербент и Шуру, убил Шах-Вали, брата шамхала Тарку, на пороге его собственного дома, и увел его жену и детей, за которых впоследствии Шамиль получил богатый выкуп. В тот раз Хаджи-Мурат и его люди проскакали 160 километров менее чем за 30 часов и, хотя преследователи шли за ними по пятам, сумели ускользнуть. Границ его смелости не было, и неудивительно, что он стал настоящим кошмаром для тех районов, жители которых подчинились России. Его боялись до такой степени, что однажды 1500 местных милиционеров под командованием русского офицера бежали от небольшого отряда мюридов с криками: «Хаджи-Мурат! Хаджи-Мурат!»
Однако в целом эта экспедиция оказалась неудачной. Русские имели преимущество в таких сражениях, и туземцы, хотя их симпатии были на стороне мюридов, были не удовлетворены ходом операции, которая сделала их объектами мести со стороны русских и не принесла ничего взамен. Они жаловались на Хаджи-Мурата, чьи многочисленные враги не упускали возможности очернить его в глазах Шамиля. Наконец Шамиль, уже начавший ревновать Хаджи-Мурата к его славе, решил избавиться от человека, чья популярность могла помешать осуществлению его честолюбивых планов, ведь недавно имам объявил преемником своего сына Кази-Мухаммада.