И вновь повествователь восхищается энергией и силой жизни кустарника: «Экая энергия! — подумал я. — Всё победил человек, миллионы трав уничтожил, а этот всё не сдается». В ранней редакции пролога было и с сильным личным эмоциональным акцентом заявленное: «„Молодец!“ — подумал я. И какое-то чувство бодрости, энергии, силы охватило меня. „Так и надо! Так и надо!“ И мне вспомнилась одна кавказская история, положение человека такое же, как и этого репейника, и человек был тоже татарин. Человек этот был Хаджи-Мурат. Вот что я знаю про это». Толстой в окончательной редакции устранил всё слишком личное и прямолинейно звучащее («Так и надо! Так и надо!»). В прологе не прозвучало и имени главного героя (оно появится в самом начале первой главы). Ясно сказано, из чего и как сложилась повесть-воспоминание: «И мне вспомнилась одна давнишняя кавказская история, часть которой я видел, часть слышал от очевидцев, а часть вообразил себе. История эта, так, как она сложилась в моем воспоминании и воображении, вот какая».
История, однако, складывалась отнюдь не легко и просто, как может показаться, а мучительно и трудно, в отличие от пролога, не претерпевшего кардинальных изменений. Красочный, мощный, символически насыщенный пролог необходимо было органично слить с давнишней историей. Первая редакция (в сущности, небольшой и камерный рассказ «Репей») явно не соответствовала прологу, выглядела как механически присоединенная к мыслям автора «художественная» иллюстрация. Не удовлетворила Толстого и следующая (всего их было десять) редакция, озаглавленная «Хазават». Толстой эту редакцию, предназначавшуюся для публикации в зарубежном издательстве «Свободное слово», четыре раза усердно переделывал и в конце концов забраковал. Попытка показать Хаджи-Мурата «как правоверного фанатичного горца-мусульманина, исповедующего идею хазавата — священной борьбы против иноверцев», оказалась неудачной, хотя она как будто бы находилась в полном соответствии с мнением Толстого, утверждавшего в довольно категоричной форме, что только «движение мысли религиозной, нравственной и ее отражение в складе жизни народов» достойны внимания историков и писателей.
Дело, конечно, здесь в том, что столь фанатичная форма религии, как священная война с иноверцами, была глубоко чужда Толстому. После многочисленных переделок он до самого необходимого минимума свел в повести все рассуждения о хазавате, исламе, религиозности Хаджи-Мурата. Подробный рассказ о том, каким образом проникся герой в отроческом возрасте идеей хазавата, как укрепилась она и слилась с ненавистью к русским под влиянием увиденной расправы над пленными горцами («не мог понять, зачем допускает Бог существование этих собак, все свои силы употребляющих на то, чтобы мучить мусульман и делать им зло. Ему представлялись все русские злыми гадинами») — всё это осталось в промежуточных редакциях. Пожертвовал Толстой и яркой сценой экзекуции с рельефно вычерченными деталями: «Дед Хаджи-Мурата не переставая шептал беззубым ртом молитву. Хаджи-Мурат дрожал, как в лихорадке, и переступал не переставая с ноги на ногу… Начальник с брюхом и запухшими глазами всё сидел и курил трубку, которую ему подавали солдаты. Хаджи-Мурат дольше не мог видеть и убежал домой». Поставил дату и пометил: «Не годится».
О религиозности героя в окончательном тексте почти ничего не говорится: упоминается лишь о регулярно совершаемых им обрядах. Не только отпал отчетливо обозначенный в ряде редакций мотив ненависти Хаджи-Мурата к русским, но была устранена и сама концепция Кавказской войны как типично колониальной, о чем говорилось с публицистической прямолинейностью: «Происходило то, что происходит везде, где государство с большой военной силой вступает в общение с первобытными, живущими своей отдельной жизнью, мелкими народами. Происходило то, что или под предлогом защиты своих, тогда как нападение всегда вызвано обидами сильного соседа, под предлогом внесения цивилизации в нравы дикого народа, тогда как дикий народ этот живет несравненно более мирно и добро, чем его цивилизаторы, или еще под всякими другими предлогами, слуги больших военных государств совершают всякого рода злодейства над мелкими народами, утверждая, что иначе и нельзя обращаться с ними».
Толстой отбросил эту характеристику Кавказской войны как неудовлетворительную, слишком упрощающую истинное положение дел, которое невозможно подвести под удобные и распространенные формулы. Устранил Толстой и исключительно резкую оценку деятельности Ермолова — зловещая фигура в девятой редакции, на Ермолова Толстой склонен был возлагать львиную долю ответственности за чрезмерные репрессии царской администрации на Кавказе.