当时战争的焦点在克里米亚。托尔斯泰对多瑙河部队的无聊生活感到厌烦，想投入战争的漩涡，便争取调往塞瓦斯托波尔。他如愿以偿，获准调到了塞瓦斯托波尔炮兵旅第三轻炮连。1854年11月7日，他到了塞瓦斯托波尔。
塞瓦斯托波尔濒临黑海，有良好港湾，在今乌克兰境内。1783年俄国人并吞克里米亚后，开始在此地建立海军基地与要塞，翌年命名为塞瓦斯托波尔，1808年辟为商埠。克里米亚战争期间，英法联军于1854年9月至1855年8月进行围攻。
1855年4月7日，托尔斯泰被调到第四棱堡。
第四棱堡是塞瓦斯托波尔最危险的地方，也是最令它的守卫者自豪的地方。托尔斯泰在这里呆了一个半月。
同僚们也许是对托尔斯泰不甚了解，也许是托尔斯泰的落落寡合、举止清高的表现伤了他们的自尊心，对托尔斯泰并不特别亲近，但是托尔斯泰的机智、活泼和快活性格无疑给他们那种平淡乏味的生活带来一股生气。从他的一位当时的同僚的回忆里，我们可以看出托尔斯泰那时的风貌来。
“托尔斯泰讲的故事和谱写的歌词，在艰苦战斗的时刻鼓舞了每一个人。他是堡垒的名副其实的灵魂。他跟我们在一起的时候，时间不知不觉地就飞逝过去了，大家都很快活……他不在的时候，比如到辛菲罗波尔去了，我们都觉得生活乏味。一天，两天，三天过去了……他终于回来了。……我们一瞧，他恰似一个浪子：脸色阴沉，两颊消瘦，露出负疚的神情。……他把我引到一边，表示后悔不已。他把自己怎样酗酒、怎样赌钱、在哪儿度过白天黑夜，统统和盘托出。这时，您想不到，他就跟一个真正罪犯一样悔恨不已，难过极了。他显得那么悲痛，叫人瞅着都不忍心。……您瞧，他就是这么一个人。”
好像炮弹就在不远的地方爆炸，仿佛四面八方都传来子弹的呼啸声，有的像蜜蜂那样嗡嗡掠过，有的就像琴弦那样吱吱作响。枪炮声惊天动地，令人十分恐惧。就在这样的环境里，托尔斯泰继续进行创作。他在这里开始写《青年》，写出了系列小说《塞瓦斯托波尔故事》。
托尔斯泰在俄国文学上第一次描绘了俄罗斯士兵和军官，描写了他们的缺点和勇敢。既写了他们浑浑噩噩，也写了他们的责任感；既写了他们的胆小，又写了他们的无畏。这些默默无闻的士兵和军官在托尔斯泰的笔下变得栩栩如生，有血有肉。
《塞瓦斯托波尔故事》在彼得堡一发表，就受到了好评。
屠格涅夫读这些故事的时候激动得热泪盈眶，巴纳耶夫给托尔斯泰写信时说全俄国都在读这些故事。皮谢姆斯基在给奥斯特洛夫斯基的信中谈到《塞瓦斯托波尔故事》时写道：“小说写得如此无情地真实，叫人读起来都觉得难过。”
据说亚历山德拉·费奥多罗夫娜皇后读《十二月的塞瓦斯托波尔》的时候曾感动得热泪盈眶，皇帝还下旨把这篇小说译成法文。
而托尔斯泰这时却在出入赌场，钻研牌术，幻想捞本。同时他脑海里又浮现出新的情景，酝酿着新的形象。这时他也在考虑怎样改善自己的经济状况的问题。他在7月8日的日记里写道：“我必须攒钱：1）为了还债；2）为了赎回庄园和让农奴获得自由。”
这年7月27日，军事委员会决定在黑溪附近与敌人决战，俄军进攻被击退，伤亡惨重。军官们对将军们的指挥无能十分愤慨，把托尔斯泰一首挖苦将军们的诗谱成了歌。这首歌在部队迅速流传起来。这件事当然破坏了托尔斯泰在军队里升迁的道路。不过这时托尔斯泰也下决心要离开军队去从事文学创作了。在9月中旬的一则日记里说：“文学之于我毕竟应当是惟一的、主要的、压倒一切其他爱好和事业的东西。”
11月已晋升为中尉的托尔斯泰被作为军事信使派往彼得堡。尽管托尔斯泰尚未脱掉军装，但他的戎马生涯已经结束。他的正式退役时间是一年以后，即1856年11月。
