Над повестью «Хаджи-Мурат» Толстой работал долго: с 1896 по 1904 год. Работал полосами, урывками, на несколько лет однажды отодвинув в сторону. Одновременно и параллельно писал и публиковал трактаты, статьи, обращения, а также художественные произведения («Воскресение», «Живой труп», «Отец Сергий», «Фальшивый купон»). Это были и срочные сочинения, злободневные, и не очень. «Хаджи-Мурат» был, пожалуй, самой несрочной и самой художественной работой, которой он особенно дорожил. Сколько бы ни «стыдился» Толстой своей «слабости», его неодолимо влекло к «пустякам», отвязаться от «эстетического» наваждения или удовлетвориться очередной более или менее сносной редакцией повести он не мог. Даже доведя работу над «Хаджи-Муратом» до художественного уровня «Отца Сергия», он, по его собственным словам, положив повесть в ящик, просто сделал передышку, вынужденный антракт — перед последним и решающим штурмом, точное время которого предсказать было невозможно. Положительно, «Хаджи-Мурат» был любимым детищем писателя, и выпустить его в свет он хотел в зрелом возрасте и одетым с иголочки. Не очень любил распространяться о повести, темнил, уклоняясь от ответов на вопросы заинтересованных лиц из мира журналистики. Не торопился. Жаль было расстаться с произведением, которое не-только «потихоньку от себя» писалось, но и во многом для себя. Со временем Толстой так сроднился с повестью, что, устояв перед частыми уговорами как Черткова, так и Софьи Андреевны, законсервировал рукопись, распорядившись опубликовать ее после смерти. Не всё же при жизни публиковать, надо кое-что и после нее оставить.

Сохранилось одно прелюбопытное воспоминание Павла Бирюкова, относящееся к 1905–1906 годам: Толстой, сконфузившись, шепотом, чтобы никто не слыхал, приблизившись к нему заблестевшими глазами, сказал: «Я писал „Хаджи-Мурата“». И сказал это «тем тоном… каким школьник рассказывает своему товарищу, что он съел пирожное. Он вспоминает испытанное наслаждение и стыдится признаться в нем». Возможно, здесь биограф Толстого допустил хронологическую неточность: следов столь поздней «подмалевки» в повести нет. Но хронологическая точность здесь не так уж и важна. Главное — ярко передано отношение Толстого к повести: любимая игрушка, что-то необыкновенно важное и сугубо личное, как счастливые и всегда памятные мгновения детства.

Между тем замысел и художественное построение повести родились сразу же — из знаменитой дневниковой записи 19 июля 1896 года:

«Вчера иду по передвоенному черноземному пару. Пока глаз окинет, ничего, кроме черной земли, — ни одной зеленой травки. И вот на краю пыльной, серой дороги куст татарина (репья), три отростка: один сломан, и белый, загрязненный цветок висит; другой сломан и забрызган грязью, черный, стебель надломлен и загрязнен; третий отросток торчит вбок, тоже черный от пыли, но всё еще жив и в середине краснеется. Напомнил Хаджи-Мурата. Хочется написать. Отстаивает жизнь до последнего, и один среди всего поля, хоть как-нибудь, да отстоял ее».

Самое первое название повести «Репей». Куст татарина (репья) из дневника перекочевал в ее пролог. Встрече с «татарином» предшествует описание лугов самой середины лета, с подробным «реестром» цветов этого времени, увиденных глазами человека, влюбленного в природу и хорошо ее знающего, который не может удержаться и не набрать большой букет цветов. К изысканному букету (своего рода икебана по фантазии Толстого) ему вдруг пришло в голову присовокупить малинового «татарина», затаившегося отдельно, в канаве. Затея оказалась плохой: «татарин» не пожелал стать частью букета, сопротивлялся изо всех сил, предпочтя гибель эстетической неволе. Оставалось с сожалением отбросить истерзанный и увядший цветок в сторону. С сожалением и восхищением: «Какая, однако, энергия и сила жизни… Как он усиленно защищал и дорого продал свою жизнь».

Далее следует описание черноземного вспаханного поля, восходящее к дневниковой записи, развернутой и превращенной в символическую картину всеобщего опустошения, всюду вносимого в природу деятельностью человека: «Экое разрушительное, жестокое существо человек, сколько уничтожил разнообразных живых существ, растений для поддержания своей жизни». Единственным признаком жизни на этом черном мертвом поле был кустик непокорного, дикого «татарина», ставшего символом борьбы-сражения, жестокой схватки на смерть: «Видно было, что весь кустик был переехан колесом и уже после поднялся и потому стоял боком, но все-таки стоял. Точно вырвали у него кусок тела, вывернули внутренности, оторвали руку, выкололи глаз. Но он всё стоит и не сдается человеку, уничтожившему всех его братий кругом его».

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

История, однако, складывалась отнюдь не легко и просто, как может показаться, а мучительно и трудно, в отличие от пролога, не претерпевшего кардинальных изменений. Красочный, мощный, символически насыщенный пролог необходимо было органично слить с давнишней историей. Первая редакция (в сущности, небольшой и камерный рассказ «Репей») явно не соответствовала прологу, выглядела как механически присоединенная к мыслям автора «художественная» иллюстрация. Не удовлетворила Толстого и следующая (всего их было десять) редакция, озаглавленная «Хазават». Толстой эту редакцию, предназначавшуюся для публикации в зарубежном издательстве «Свободное слово», четыре раза усердно переделывал и в конце концов забраковал. Попытка показать Хаджи-Мурата «как правоверного фанатичного горца-мусульманина, исповедующего идею хазавата — священной борьбы против иноверцев», оказалась неудачной, хотя она как будто бы находилась в полном соответствии с мнением Толстого, утверждавшего в довольно категоричной форме, что только «движение мысли религиозной, нравственной и ее отражение в складе жизни народов» достойны внимания историков и писателей.

Дело, конечно, здесь в том, что столь фанатичная форма религии, как священная война с иноверцами, была глубоко чужда Толстому. После многочисленных переделок он до самого необходимого минимума свел в повести все рассуждения о хазавате, исламе, религиозности Хаджи-Мурата. Подробный рассказ о том, каким образом проникся герой в отроческом возрасте идеей хазавата, как укрепилась она и слилась с ненавистью к русским под влиянием увиденной расправы над пленными горцами («не мог понять, зачем допускает Бог существование этих собак, все свои силы употребляющих на то, чтобы мучить мусульман и делать им зло. Ему представлялись все русские злыми гадинами») — всё это осталось в промежуточных редакциях. Пожертвовал Толстой и яркой сценой экзекуции с рельефно вычерченными деталями: «Дед Хаджи-Мурата не переставая шептал беззубым ртом молитву. Хаджи-Мурат дрожал, как в лихорадке, и переступал не переставая с ноги на ногу… Начальник с брюхом и запухшими глазами всё сидел и курил трубку, которую ему подавали солдаты. Хаджи-Мурат дольше не мог видеть и убежал домой». Поставил дату и пометил: «Не годится».