августа 1855 года был в Севастополе. Долгое время жил на 4-м бастионе, часто подвергавшемся нападениям, командовал батареей в сражении при Чёрной , был при бомбардировке во время штурма Малахова Кургана. Толстой, несмотря на все житейские тяготы и ужасы осады, в это время написал рассказ «Рубка леса», в котором отразились кавказские впечатления, и первый из трёх « Севастопольских рассказов» — «Севастополь в декабре 1854 г.». Этот рассказ он отправил в «Современник». Он был быстро издан и с интересом прочитан всей Россией, произведя потрясающее впечатление картиной ужасов, выпавших на долю защитников Севастополя. Рассказ был замечен российским Александром III; он велел беречь даровитого офицера.
Ещё при жизни императора Николая I Толстой предполагал издавать вместе с офицерами-артиллеристами «дешёвый и популярный» журнал «Военный листок», однако проект журнала Толстому осуществить не удалось: «На проект мой Государь император всемилостивейше изволил разрешить печатать статьи наши в „Инвалиде“» — горько иронизировал Толстой по этому поводу.
За нахождение во время бомбардирования на Язоновском редуте четвёртого бастиона, хладнокровие и распорядительность.
— Из представления к ордену Святой Анны 4-й ст.