1856年11月26日，他“因病”获准能以炮兵中尉衔退伍。他改善农奴状况的方案已宣告失败。他要娶瓦列里娅的幻想已破灭。他这时闲云野鹤，了无牵挂，便决定出国游历。
这次出国1月29日出发，8月8日归来，历时半年，游览了法国、瑞士、德国一些地方。
1857年1月29日，托尔斯泰乘驿马离开莫斯科去华沙，从莫斯科到华沙1269俄里，托尔斯泰走了五天，路上思考了《失落者》的写作问题。
一到华沙，托尔斯泰就给在巴黎的屠格涅夫去电报问他是否准备在巴黎久住。屠格涅夫立即回电说准备久住，而且涅克拉索夫也跟他在一起。接到回电以后，托尔斯泰立即乘火车动身去巴黎，2月9日（公历21日）到达巴黎。
当天，托尔斯泰就去找屠格涅夫和涅克拉索夫。但出乎意料，见面的印象并不快乐。
第二天，他就给鲍特金写信说：
“我昨天抵达巴黎，并在这儿遇到了屠格涅夫和涅克拉索夫。他们俩都脸色忧郁，愁眉不展，对生活满腹牢骚——整天无所事事，郁郁寡欢，似乎他们每人都有自己的难言之苦。不过我很少见到他们。屠格涅夫的神经过敏逐渐变成了一种可怕的病，此病同他那平易近人的作风和仁慈心肠结合在一起——真是一种奇怪的现象。这种最初的印象使我感到忧心忡忡，更何况我在莫斯科生活了一段之后，至今还处于极度的lebens-froh①之中。我对德国虽然只是匆匆一瞥，但它给我留下了强烈而又愉快的印象。”
①德语：乐观情绪。
在巴黎见到托尔斯泰后，屠格涅夫最初的印象是不错的。他在给沃隆斯基的一封信里说：“托尔斯泰在此地。在他的身上，向好的方面已起了相当大的变化。”可是很快屠格涅夫便感到失望了。他在给科尔巴辛的信中写道：“我依然无法跟托尔斯泰真正接近起来，因为我们的看法实在凑不到一块儿。”
托尔斯泰在日记里也说：“不，我在避开他。我对他的贡献做了充分赞扬，从各个方面迎合他，可是没法取得一致。”
尽管如此，两位作家仍然经常见面，并且一同前往第戎。看来，他们俩都有接近的愿望，但是他们的性格、观点、修养、处事态度的不同又使他们不能亲密起来。
托尔斯泰在巴黎住了将近两个月，印象本来一直是极好的。他1857年3月24日—25日（公历4月5—6日）给鲍特金的信里讲得极为详尽，我们不妨引一段看看：
“我仍旧住在巴黎，眼看快两个月了；我无法预料：什么时候这个城市才会使我对它失去兴趣，这种生活才会失去它的魅力。我是一个十足的不学无术的人；我在任何地方也没有像在这里这样强烈地感到这一点。因此，单凭这一点我就可以为我在这里的生活感到满足和幸福；况且，在这里我也感到这种无知并非不可救药。再就是艺术上的享受，罗浮宫、凡尔赛宫、高等音乐学校、四重奏、剧院、CollègedeFranse①②和索尔蓬纳里的讲课，而主要的是能够享受到社会自由，我在俄国对这种自由甚至是毫无概念的。凡此种种，使我不能早于两个月，即不能在矿泉疗程开始之前离开巴黎或巴黎近郊的乡村，近日内我想迁到那里去住。”
①法语：法兰西学院。
②16—17世纪时为巴黎大学神学院，后指巴黎大学文理学院，泛指巴黎大学。
可是就在写完上面那段话的第二天，他去观看了一个执行死刑的场面。这件事急剧地改变了他的看法。关于这件事情，他在上文所引的给鲍特金的那封信里接着说：
“上面这些是我昨天写的，被人打断了。而今天我的心情完全变了。
今天早晨，我做了一件愚蠢而冷酷的事——乘车去看执行死刑的情景。
再加上两周来这里的天气一直十分恶劣，我觉得很不舒服，我一度处于一种令人厌恶的神经质的情绪之中，因此这种场面给我留下的印象将使我长久不得安宁。我在战场和高加索见过许多可怕的场面，但是即使当着我的面把一个人撕成碎块，也没有用这台精巧雅致的机器在一瞬间把一个身强力壮的活人杀死那么令人反感。因为在战场上占上风的不是理智的意志，而是感情的冲动；而这儿却周密细致地使杀人变得不动声色，方便易行，没有丝毫壮观之处。……这里几天前逮捕了许多人，破获了一个企图在剧院谋杀拿破仑的案件，案犯也将于近日内处决。但是今后我肯定不会去看这种场面，也不会去为任何政府效力了。”
他稍后在5月13日和25日的创作笔记里写道：“所有的政府，就其善恶而论，都是一模一样的”，“最好的理想境界便是无政府状态”。
他之所以得出这种结论，我们认为很可能跟这次观感有关。
看完了死刑以后，托尔斯泰久久地吃不下饭去，夜里常常做噩梦。
第二天醒来觉得不舒服，刚想要读书，就产生了一个想法：离开巴黎。
可是上哪儿去呢？
他当时心绪不佳，极需找一个体贴入微的亲近的人谈谈。他想起了当时在日内瓦的堂姑亚历山德拉·安德烈耶夫娜·托尔斯泰娅。
第二天，托尔斯泰就离开巴黎去日内瓦了。
到达日内瓦的第二天，托尔斯泰就去找堂姑。
亚历山德拉·安德烈耶夫娜是尼古拉一世的女儿玛丽亚·尼古拉耶夫娜的女官，她的妹妹伊丽莎白·安德烈耶夫娜是尼古拉一世的外孙女的教师，她们当时跟公主一家住在日内瓦附近的波卡日别墅里。
亚历山德拉·安德烈耶夫娜在其《回忆录》里说，托尔斯泰一见到他们就说：
“我是从巴黎直接来找你们的。巴黎那么使我厌恶，险些使我精神失常。那儿的一切都叫我看够了！……第一，在我所住的maisongarnie（法文：公寓）里，住了三十六个ménages（法文：家庭），其中19个是非法同居。这使我十分愤慨。后来我想试试自己的胆量，去看了一次斩决犯人的场面。看完以后睡不着觉，不知躲到哪儿好。幸好偶尔听说您在日内瓦，便拼命赶到您这里，相信您能救我。”
亚历山德拉·安德烈耶夫娜接着写道：“的确，他把心里话都说出来之后，就很快平静下来，我们一起过得好极了。”
托尔斯泰很喜欢这位堂姑。在4月12日的日记里，他写道：“亚历山德拉的微笑美极。”他在4月19日（公历5月11日）的日记里写道：
“跟两位堂姑在一起多么愉快啊。”“十分，十分愉快。”“我很想爱她，这实在太