Толстой попал на Кавказскую войну в 1851 году, в возрасте 23 лет, участвовал во многих боевых стычках и историю Хаджи-Мурата прекрасно знал. Но полностью "пазл" повести о знаменитом наибе Шамиля сложился у писателя лишь спустя полвека, когда Толстой увидел искалеченный тележным колесом, но упрямо встающий репейный куст и написал в дневнике, что он напомнил ему Хаджи-Мурата: "Молодец!" - подумал я... Так и надо, так и надо". Большая часть повести была готова к осени 1902 года, последние правки датируются декабрем 1904 года. Однако при жизни Толстого по решению самого писателя повесть не публиковалась. Впервые она была издана в "Посмертных художественных произведениях Л. Н. Толстого" в Москве в 1912 году с цензурными изъятиями, а без купюр была издана в России в 1917 году. В 1903 году, рассказывая американскому журналисту Джеймсу Крилмену о своей работе, Толстой говорил: "Это - поэма о Кавказе, не проповедь. Центральная фигура - Хаджи-Мурат - народный герой, который служил России, затем сражался против нее вместе со своим народом, а в конце концов русские снесли ему голову. Это рассказ о народе, презирающем смерть".