Дело приняло решительный оборот с назначением в 1856 году кавказским наместником князя Барятинского. Пользуясь личным влиянием на императора Александра II, он собрал на Кавказе до тех пор небывалой численности двухсоттысячное войско и значительную долю этих сил направил против Чечни, Ичкерии и Дагестана, объединенных в это время под начальством хорошо известного Шамиля.
Талант, энергия этого вождя, фанатизм, отвага признававших его своим имамом горцев, - все было сломлено под давлением навалившейся на них громадной силы, руководимой ни перед чем не останавливавшимся Евдокимовым: в 1857 году пала перед ним резиденция Шамиля в центре Ичкерии, аул Ведено, а в 1859 году сдался князю Барятинскому и сам Шамиль в своей новой дагестанской твердыне - Гунибе.
Князь Барятинский до назначения своего кавказским наместником является в начале 50-х годов на Северном Кавказе начальником левого фланга кавказской армии.
Вот к этому-то времени относится и появление на Кавказе Льва Николаевича Толстого, и к этому времени и к этой местности относятся события, описанные Львом Николаевичем в его кавказских рассказах: "Набег", "Казаки", "Рубка леса", "Встреча в отряде".
Из Астрахани оба брата поехали на почтовых через Кизляр в станицу Старогладовскую, к месту служения Николая Николаевича. Лев Николаевич явился на Кавказ частным лицом и поселился вместе со своим братом.
Первое впечатление, произведенное на него Кавказом, не было ошеломляющим. Он так описывает его в письме к своей тетке, вскоре по приезде на Кавказ:
"Je suis arrive sain et sauf, mais un peu triste vers la fin du mois de mai dans la Старогладовская. J'y ai vu de pres le genre de vie que mene Nicolas, et j'y ai fait la connaissance des officiers qui font la societe. Le genre de vie n'est pas tres attrayant, a ce qu'il m'a para d'abord, puisque le pays, que je m'attendais a trouver fort beau ne l'est pas du tout. Comme la станица est situee aur un terrain bas, il n'y a bas de point de vue et puis le logement est mauvais de meme que tout ce qui fait le comfort de la vie. Pour ce qui est des officiers, ce sont, comme vous pouvez vous figurer, des gens sans education, mais avec cela de tres braves gens et surtout aimant beaucoup Nicolas.
Алексеев, son chef, est un petit bonhomme белокуренький tirant sur le roux с усиками и бакенбардами, говорящий пронзительным голосом, mais excellent chretien, rappelant un peu А. С. Волков, mais pas cafard comme lui. Puis Б... un jeune officier - enfant et bon enfant, rappelant Петрушка. Puis un vieux capitaine Билковский des kosaks de l'Oural - un vieux soldat simple, mais noble, brave et bon. Je vous avouerai qu'au commencement beaucoup de choses me choquaient dans cette societe, mais je me suis habitue, sans toutefois me Her avec ces messieurs. J'ai trouve un heareux moyea dans lequel il n'y a ni fierce ni familiarite. Au reste en ceci je n'avais qu'a suivre l'exemple de Nicolas". (*)
