В Петербурге Толстой знакомится с Ф.И. Тютчевым, специально посетившим его, чтобы выразить восхищение севастопольскими рассказами, А.А. Фетом, Н.А. Некрасовым, И.С. Тургеневым, И.А. Гончаровым, А.Ф. Писемским, Я.П. Полонским, А.В. Дружининым, П.В. Анненковым, В.Л. Боткиным и другими писателями и критиками. К этому периоду относится работа над рассказом «Метель» (1856), представляющим собой реплику пушкинской «Капитанской дочки», и повестью «Два гусара» (1856), полемически направленной против «вопросов» современности и демонстративно разрешавшей одну из немаловажных альтернатив русской литературы («отцы и дети») в пользу «отцов». Полемика с «шестидесятниками» продолжится и в незаконченном романе «Декабристы», и в уже открыто пародирующей идеи Чернышевского пьесе «Заражённое семейство», при жизни Толстого не публиковавшейся. Рассказ «Утро помещика» (1856, «Отечественные записки») также связан с современностью, но не только проблематикой взаимоотношений помещика и крестьян, а и поисками героя, способного осуществить идеал Толстого – объединение людей на основе «настоящей жизни».
В 1857 г. Толстой совершает поездку в Западную Европу (посещает Францию, Германию, Италию, Швейцарию). В Париже осматривает гробницу Наполеона, после чего записывает в дневнике; «Обоготворение злодея, ужасно». Противовес этому «обоготворению» злодеев он будет искать в «Войне и мире». Став свидетелем смертной казни, Толстой ещё больше укрепляется во мнении, что «государство есть заговор не только для эксплуатации, но главное для развращения граждан», и даёт себе обещание: «Я… никогда не буду служить нигде никакому правительству». Тяжёлые заграничные впечатления отразились в рассказе «Из записок князя Д. Нехлюдова. Люцерн» (1857, «Современник»),
В рассказе «Три смерти» (1858), во многом этапном для молодого Толстого, показана смерть барыни, которая «гадка и жалка», умирая в «разладе» с миром, смерть старого ямщика («его религия – природа», по словам Толстого) и смерть дерева, «ясенки», из которого молодой ямщик собирается изготовить крест на могиле умершего товарища и которое умирает «спокойно, честно и красиво». Рассказ, а скорее философская притча о превосходстве в смертный час дерева над человеком, содержит главные концепты дальнейшего творчества Толстого: «Смерть», «Истина», «Гармония со всем миром». Но как соединить рефлектирующее сознание с бессознательной природной гармонией? В рассказе «Альберт» (1858) Толстой отдаёт предпочтение первому, в повести «Казаки» (1863) – второму.
Замысел повести «Казаки» восходит к намерению 1852 г. писать очерки о Кавказе. У Толстого были также планы соединить повесть, герою которой приданы некоторые автобиографические черты, с «Четырьмя эпохами развития». Казалось бы, сюжет «Казаков» построен на обычном романтическом мотиве бегства героя из цивилизованного мира и столкновения с миром первобытно-природным. В критике не раз указывалось даже на сходство названий «Казаки» и «Цыганы», на созвучие «Оленина» и «Алеко». Не случайно и упоминание в тексте повести о «Куперовом Патфайндере» (романе американского писателя Ф. Купера «Следопыт»). Однако кавказская и военная тема в творчестве Толстого с самого начала была связана с развенчанием романтического комплекса. Герой Толстого продолжает испытывать чувство горькой отделённости от окружающих (Николенька в трилогии – от родных и товарищей по университету, Оленин – от казаков, Нехлюдов в «Утре помещика» – от крестьян), но в то же время приобретает некое весьма важное знание об общих закономерностях жизни и её сложности, недоступное более цельным и непосредственным натурам.
Оленин и дядя Ерошка – это не просто человек «цивилизованный» и человек «естественный», а посвящаемый и посвящающий. Необходимое для создания непривычной обстановки уединение (пустыня) заменено в «Казаках» перемещением героя из центра на периферию. Сохраняет своё значение инициационный мотив испытания смертью и усиливается звучание мотива охоты (охотятся не только Оленин с Ерошкой, но и на них; не только Лукашка на горцев, но и горцы на Лукашку).
Новизна толстовского героя в том, что мотив охоты трансформируется в сознании Оленина в мотив любви, объединения со всем миром. Он хочет «раскидывать на все стороны паутину любви: кто попадётся, того и брать». «Паутина любви» – образ, навеянный чтением Стерна («web of kindness» – англ.), имеющий большое значение в дневниках Толстого и в «Войне и мире». Так что Оленина можно уже назвать адептом той новой «практической религии», которой Толстой собирался посвятить своё творчество.