Будучи юнкером, Лев Николаевич оставался два года на Кавказе, где участвовал во многих стычках с горцами и подвергался опасностям военной кавказской жизни. Он имел права на Георгиевский крест, однако так и не получил его. Во время Крымской войны, вспыхнувшей в конце 1853 года, Толстой перевёлся в Дунайскую армию, участвовал в сражении при Ольтенице и в осаде Силистрии, а с ноября 1854-го по конец августа 1855 года был в Севастополе.
Стела в память участника обороны Севастополя 1854—1855 гг. Л. Н. Толстого у четвёртого бастиона

Долгое время жил на 4-м бастионе, часто подвергавшемся нападениям, командовал батареей в сражении при Чёрной, был при бомбардировке во время штурма Малахова Кургана. Толстой, несмотря на все житейские тяготы и ужасы осады, в это время написал рассказ «Рубка леса», в котором отразились кавказские впечатления, и первый из трёх «Севастопольских рассказов» — «Севастополь в декабре 1854 г.». Этот рассказ он отправил в «Современник». Он был быстро издан и с интересом прочитан всей Россией, произведя потрясающее впечатление картиной ужасов, выпавших на долю защитников Севастополя. Рассказ был замечен российским императором Александром II, он велел беречь даровитого офицера.

Ещё при жизни императора Николая I Толстой предполагал издавать вместе с офицерами-артиллеристами «дешёвый и популярный» журнал «Военный листок», однако проект журнала Толстому осуществить не удалось: «На проект мой Государь император всемилостивейше изволил разрешить печатать статьи наши в "Инвалиде"», — горько иронизировал Толстой по этому поводу.

За оборону Севастополя Толстой был награждён орденом Св. Анны с надписью «За честь», медалями «За защиту Севастополя 1854—1855» и «В память войны 1853—1856 гг.». Впоследствии он был награждён ещё двумя медалями «В память 50-летия защиты Севастополя». Толстой, пользуясь репутацией храброго офицера и окружённый блеском известности, имел все шансы на карьеру. Тем не менее, его карьера оказалась испорченной написанием нескольких сатирических песен, стилизованных под солдатские. Одна из этих песен была посвящена неудаче военной операции 4 (16) августа 1855 года, когда генерал Реад, неправильно поняв приказание главнокомандующего, атаковал Федюхины высоты. Песня под названием «Как четвёртого числа, нас нелёгкая несла горы отбирать», задевавшая целый ряд важных генералов, имела огромный успех. За неё Льву Николаевичу пришлось держать ответ перед помощником начальника штаба А. А. Якимахом. Сразу после штурма 27 августа (8 сентября) Толстой был послан курьером в Петербург, где он закончил «Севастополь в мае 1855 г.» и написал «Севастополь в августе 1855 г.», опубликованный в первом номере «Современника» за 1856 год уже с полной подписью автора. «Севастопольские рассказы» окончательно укрепили его репутацию как представителя нового литературного поколения, и в ноябре 1856 года писатель навсегда оставляет военную службу.