Но еще в течение года после написания «Репья» Толстой не приступал к работе над «Хаджи-Муратом», будучи всецело занят другими работами, хотя сюжет этот всё более и более привлекал его внимание. 14 октября 1897 г. он записал в Дневнике: «К Хаджи Мурату подробности: 1. Тень орла бежит по скату горы. 2. У реки следы по песку зверей, лошадей, людей. 3. Выезжая в лес, лошади бодро фыркают. 4. Из куста держи-дерева выскочил козел». В Дневнике 16 октября 1897 г. записано: «Вчера вечером и нынче хотел писать Хаджи Мурата. Начал. Похоже что-то, но не продолжал потому, что не в полном обладании. Не надо портить и насильно».
С. А. Толстая в своих записках «Моя жизнь» пытается объяснить причину неуспеха работы Толстого так: «Лев Николаевич брался и за излюбленного им «Хаджи-Мурата», но с этим делом не пошло и пришлось оставить. Художественные работы, на мой взгляд, всегда требовали полного спокойствия, как физического, так нравственного, духовного. Без него работа не шла. А спокойствия было всё меньше и меньше». Тем не менее после первой неудачной попытки 15—16 октября 1897 г. Толстой через месяц возобновляет работу над «Репьем». В Дневник 11 ноября 1897 г. занесено: «С утра писал Хаджи-Мурата — ничего не вышло. Но в голове уясняется, и очень хочется».
Написанное 15—16 октября и 11 ноября 1897 г. представляет собой начало второй незаконченной редакции произведения (варианты №№ 2—11). Здесь четыре главы. Тема развита шире, чем в «Репье», композиция иная. В главе I описывается выход солдат в секрет; в гл. II — вечер у молодого Воронцова; в главе III — пребывание Хаджи-Мурата с мюридом Асланбеком у кунака Саффедина, в главе IV — рубка леса, смерть Никитина, выезд молодого Воронцова и встреча с Хаджи-Муратом, прием Хаджи-Мурата Марьей Васильевной, столкновение молодого Воронцова с Меллер-Закомельским.
Материалом для гл. I этой редакции послужила книга Зиссермана «Двадцать пять лет на Кавказе», ч. II, стр. 288, для остального — «Воспоминания» В. А. Полторацкого. События происходят в передовой крепости Шахгири, или по-русски Воздвиженской, в которой Толстой бывал в своей молодости. В рассказе выведен Полторацкий, первоначально названный настоящей своей фамилией, затем «Полторасовым», потом «краснолицым» и «широколицым офицером» без фамилии. Толстой знал Полторацкого в бытность на Кавказе; вспомнить его внешность помог портрет, приложенный к журналу «Исторический вестник» за 1895 г. Молодой Воронцов и его жена Марья Васильевна отчасти описаны по личным воспоминаниям, так как Толстой встречался с ними на Кавказе, отчасти по «Воспоминаниям» Полторацкого. Первая глава новой редакции произведения далась Толстому с большим трудом. Листы, на которых она написана, испещрены бесчисленными вставками и исправлениями. С еще большим упорством Толстой работал над коротенькой третьей главой, принимаясь за нее девять раз. Страницы ее едва поддаются прочтению. Толстой записал по поводу данной рукописи: «не вышло» и прекратил работу над нею.
В Дневнике 14 ноября 1897 г. записано: «Думал в pendant к Хаджи Мурату написать другого русского разбойника Григория Николаева...» (Выведен под именем дворника Василия в повести Толстого 1904 г. «Фальшивый купон».) О возобновлении работы над «Хаджи-Муратом» Толстой 17 ноября 1897 г. писал жене: «Начал новое — художественное, кавказский рассказ, который me hante2500 — уже давно».2501 Через три дня, 20 ноября, он писал ей: «мысли же и занятия мои направлены на кавказскую повесть, которой мне совестно заниматься, тем более, что она нейдет, но от которой не могу отстать».2502
Написанное 17—20 ноября 1897 г. является началом третьей редакции повести (варианты №№ 12—16). Содержание ее существенно отличается от содержания двух предыдущих. Дана сцена обеда в тифлисском дворце наместника Кавказа Воронцова, сцена приема Воронцовым Хаджи-Мурата, включено письмо Воронцова к Чернышеву. Заканчивается рукопись рассказом Хаджи-Мурата Лорис-Меликову о своей прошлой жизни. Две главы, в одной из которых описывается ранняя пора жизни Хаджи-Мурата (материалом для нее послужили «Воспоминания муталима», помещенные в «Сборнике сведений о кавказских горцах», вып. I и II), а в другой приводится рассказ Хаджи-Мурата Лорис-Меликову о своем прошлом. Затем они были исключены Толстым из рукописи.
Писавшаяся в течение четырех дней (17—20 ноября 1897 г.) третья редакция «Хаджи-Мурата» не удовлетворила Толстого так же, как и первые две.
20 ноября 1897 г. он записал в Дневнике: «Много обдумал Хаджи Мурата и приготовил материалы. Всё тон не найду».