В 1854 году в журнале «Современник» печатаются стихотворения Толстого и «Досуги Козьмы Пруткова», а летом Толстой предпринимает усилия по созданию партизанского отряда на балтийском побережье – идёт Восточная война. 28 марта 1855 года высочайшим приказом младший чиновник II Отделения статский советник и церемониймейстер граф Толстой определён майором в Стрелковый полк Императорской Фамилии, расквартированный в селе Медведь под Новгородом. Зачислен в списки первой роты первого батальона. В последующие месяцы Толстой довольно часто отлучается из полка по личным и литературным причинам, пока в декабре, уже в Одессе, не присоединяется к своей части. В феврале 1856 года Толстой, исполняющий обязанности батальонного командира, заболевает тифом. Александру II, недавно вступившему на престол, ежедневно докладывают телеграммами о состоянии его здоровья За ним ухаживает приехавшая в Одессу С.А. Миллер. Выздоровев, Толстой отправляется с возлюбленной в путешествие по Крыму, а в августе приезжает в Москву для участия в коронационных торжествах. Толстой вместе с штаб-офицерами полка «назначен для принятия балдахинов в день коронования». 26 августа он произведён в подполковники и назначен флигель-адъютантом к императору. К осени того же года относится сближение с А.С. Хомяковым и К.С. Аксаковым. В октябре при переформировании Стрелкового полка в б а т а л и о н по распоряжению императора оставлен в его штате с правом бессрочного отпуска в мирное время. Тогда же назначается делопроизводителем в Комитете по делам о раскольниках. 10 ноября умирает дядя, Лев Алексеевич Перовский, с которым Толстой находился в тёплых родственных отношениях. В это же время он знакомится с Л.Н. Толстым.
2 июня 1857 года умирает Анна Алексеевна – мать Толстого. Сын и отец, К.П. Толстой, проводят ночь у гроба графини. А.К. Толстой с этой поры высылает отцу ежемесячную пенсию (около 4000 р. в год). Толстой телеграфирует о смерти матери в Париж Софье Андреевне Миллер (Анна Алексеевна была против этого союза, как, впрочем, и вообще очень ревниво относилась к любой сыновней избраннице).
Вскоре Толстой и С.А. Миллер вместе с семьей и прислугой её брата поселяются в Пустыньке, близ Петербурга. Когда в ноябре скончался ещё один дядя Толстого, генерал-адъютант Василий Алексеевич Перовский, по наследству Перовскому досталось имение Мелас в Крыму.
1 января 1858 года Толстой возвратился в Петербург, где произошло окончательное воссоединение с Софьей Андреевной, которая в это время ведёт дело о разводе с мужем. В журнале «Русская беседа» (№1) публикуется его поэма «Иоанн Дамаскин». 17 апреля Толстому пожалован орден Св. Станислава 2-й степени, а летом этот упоённый жизнью человек присутствует в Петербурге на спиритических сеансах знаменитого Юма.
