В 1854 Толстой получил назначение в Дунайскую армию, в Бухарест. Скучная штабная жизнь вскоре заставила его перевестись в Крымскую армию, в осажденный Севастополь, где он командовал батареей на 4-м бастионе, проявив редкую личную храбрость (награжден орденом св. Анны и медалями). В Крыму Толстого захватили новые впечатления и литературные планы (собирался в т. ч. издавать журнал для солдат), здесь он начал писать цикл «севастопольских рассказов», вскоре напечатанных и имевших огромный успех. Первые произведения Толстого поразили литературных критиков смелостью психологического анализа и развернутой картиной «диалектики души» (Н. Г. Чернышевский). Некоторые замыслы, появившиеся в эти годы, позволяют угадывать в молодом артиллерийском офицере позднего Толстого-проповедника: он мечтал об «основании новой религии» «религии Христа, но очищенной от веры и таинственности, религии практической» .
В кругу литераторов и за границей
В ноябре 1855 Толстой приехал в Петербург и сразу вошел в кружок «Современника» (Н. А. Некрасов, И. С. Тургенев, А. Н. Островский, И. А. Гончаров и др.), где его встретили как «великую надежду русской литературы» (Некрасов). Толстой принимал участие в обедах и чтениях, в учреждении Литературного фонда, оказался вовлеченным в споры и конфликты писателей, однако чувствовал себя чужим в этой среде, о чем подробно рассказал позднее в «Исповеди» (1879−82): «Люди эти мне опротивели, и сам себе я опротивел». Осенью 1856 Толстой, выйдя в отставку, уехал в Ясную Поляну, а в начале 1857 за границу. Он побывал во Франции, Италии, Швейцарии, Германии (швейцарские впечатления отражены в рассказе «Люцерн»), осенью вернулся в Москву, затем в Ясную Поляну.