Николай I умер 18 марта 1855 года. Севастополь был сдан 27 августа 1855 года, когда французские войска овладели господствующим над городом Малаховым курганом. Лишь к этому времени формирование полка наконец-то закончилось. Офицеры и стрелки были одеты в невиданную ранее форму: красные рубахи, полукафтаны, широкие штаны, меховые шапки. По преданию, они были пошиты по эскизам Алексея Толстого и Владимира Жемчужникова. Новый император Александр II, не раздумывая, утвердил инициативу своего любимца. В таком виде полк выступил в поход через Москву на Одессу. Новая форма по французскому образцу была введена также в армии и гвардии. В обществе это встретило неудовольствие, поскольку момент для таких перемен был явно неподходящим.

Накануне выступления 26 августа 1855 года в Царском Селе на Софийской площади состоялся смотр стрелкового полка в присутствии Александра II.

Царя приветствовали пением полкового гимна, получившего название «Слава». Однополчане поговаривали, что А. К. Толстого ждёт венец Жуковского — автора «Певца во стане русских воинов».

По пути А. К. Толстой написал короткое стихотворение, вызванное действительным случаем, произошедшим в Севастополе:

Полку надлежало занять оборону вблизи Одессы на побережье Чёрного моря. Штаб расположился в деревне Севериновке, а первый батальон — в болгарском селе Катаржи (таких сёл около Одессы было несколько).

В военных действиях полк не участвовал, но, тем не менее, нёс огромные потери. Эпидемии оказались страшнее неприятельских пуль. А. К. Толстой — Софье Андреевне Миллер 20 декабря 1855 года: «Везде тиф, диссентерия, у нас нет докторов. Оба наших — один из которых, Сидоров, болен — находятся в Севериновке со штабом; больных перевозят туда то на волах, то на лошадях; у нас нет госпиталя, больные размешены по избам — один на другом, умирают лицом к лицу; места совсем нет; выздоравливающие разбросаны по всей Севериновке, и присмотру за ними никакого нет; они часто убегают, едят вредные вещи у хозяев и опять заболевают. Вчера третья рота перевозила своих больных через наше село; один из них скончался в дороге, и я принял его тело в мой домик. Я хотел оставить его на всю ночь, но нашли возможность отвести для него пустую землянку… Сегодня я возил туда священника и присутствовал на панихиде. Какие хорошие люди болгары, гостеприимные, добродушные; они одеты точно люди на картинах Каналетто — курящие трубки на площади св. Марка. Во всяком доме находятся образа православные… Они ненавидят турков, от которых бежали, и говорят библейским славянским языком».

В январе следующего года А. К. Толстой съездил в Одессу. Вот его впечатления (письмо Софье Андреевне Миллер от 16 января 1856 года):

«Бедному Бобринскому очень плохо; его обливали холодной водой, что его немного привело в себя…

Самые утешительные слова докторов „Надежда не потеряна“…

…Я навещал пленных французов и встречал их иногда на улицах; я с ними говорил и находил их учтивыми и приличными, несмотря на то, что они были из простых солдат. Что же касается до англичан, я не понимаю, что мы с ними так церемонимся, — просто беспокойные грубияны, которых я бы быстро привёл в порядок, если был бы я градоначальник.

Турки лучше англичан, — и англичане их преследуют; эти бедняки достали себе какую-то жестяную посуду, чтобы черпать воду… Когда англичанин встречает турка, он вырывает у него посуду и давит её ногами».

Тиф был беспощаден. Более половины полка болело; из 3200 человек в строю оставалось менее 1500. За сутки умирало до 20 человек. В конце концов свалились в тифу и В. М. Жемчужников и А. К. Толстой. Узнав об этом, Александр II приказал, чтобы ему ежедневно докладывали о состоянии друга.

Из офицеров здоровыми на ногах оставались всего лишь трое или четверо. Алексей Толстой долгое время лежал в бреду, и первое, что он увидел, придя в сознание, было лицо любимой женщины. Софья Андреевна, в качестве сестры милосердия, срочно выехала к своему возлюбленному. Ещё одним неожиданным гостем был другой двоюродный брат — уже упомянутый художник Лев Жемчужников.

Заботливый уход вскоре поднял Алексея Константиновича с постели. Впоследствии Лев Жемчужников вспоминал: «Здоровье Алексея Толстого становилось лучше с каждым днём. Помню, с каким удовольствием я усадил его в коляску в первый раз по выздоровлении, ещё не совершенно окрепшего, и повёз покататься к морю, он был в восторге, вдыхал полной грудью воздух, но утомился. Впрочем, он скоро вполне поправился, и я с ним отправился гулять, но куда?.. Куда могла увлечь нас только безрассудная молодость… между прочим в каменоломни, где бывали грабежи. Он и я запаслись свечами, спичками, и так как я там бывал и слышал о случавшихся там несчастных приключениях, то запасся револьвером, а Толстой, хотя и взял револьвер, но надеялся более на охотничий нож, который, как он говорил, не изменит. Одно его смущало — что он не чувствовал в себе той силы, которою обладал прежде. Подойдя к пещерам каменоломен, мы зажгли свечи, вооружились и отправились внутрь. Но увы! исходив пещеры в разных направлениях, попадая то в ямы, то в лужи, мы ровно никого (грабителей. — В. Н.) не нашли и, пристыженные, разочарованные, с досадой вернулись домой» [40].

В марте 1856 года в полку было получено известие о подписании мира в Париже. Оно было встречено всеобщим негодованием. Действительно, казалось, что война только начинается, и сдан-то всего лишь Севастополь (другими словами — одна крепость). Неудачи в Крыму компенсировались успехами на Кавказе, где русские войска заняли Карс. Правда, мир не оказался чрезмерно унизительным, хотя для России и невыгодным. Но было обидно возвращаться домой, так и не встретившись с врагом. Единственно, Лев Жемчужников, побывавший ранее в Севастополе и наглядевшийся на царившие в этом героическом городе ужасы, шумно радовался, что наконец-то прекратилось бесцельное кровопролитие. Он даже сцепился с Алексеем Бобринским, и они наговорили друг другу много жестоких слов. Дело дошло до вызова на дуэль. С большим трудом Толстому и Владимиру Жемчужникову удалось их помирить.

Весной этого года было решено совершить поездку по Крыму. В путь отправились Алексей Толстой, Софья Андреевна Миллер, Владимир Жемчужников и Алексей Бобринский. Впечатления вояжа описаны А. К. Толстым в стихотворном цикле «Крымские очерки». На пути всюду были следы отгремевшей войны. Вот что поэт нашёл в имении своего дяди Льва Алексеевича Перовского:

(«Крымские очерки. 9». Лето 1856)

Но всё же хотелось верить, что жизнь входит в мирный круговорот. Он адресует Софье Андреевне проникновенные строки: