Известно, что А. К. Толстой написал несколько так называемых «военных песен», но до нас, кроме вышеприведённой, дошла ещё только одна:
Николай I умер 18 марта 1855 года. Севастополь был сдан 27 августа 1855 года, когда французские войска овладели господствующим над городом Малаховым курганом. Лишь к этому времени формирование полка наконец-то закончилось. Офицеры и стрелки были одеты в невиданную ранее форму: красные рубахи, полукафтаны, широкие штаны, меховые шапки. По преданию, они были пошиты по эскизам Алексея Толстого и Владимира Жемчужникова. Новый император Александр II, не раздумывая, утвердил инициативу своего любимца. В таком виде полк выступил в поход через Москву на Одессу. Новая форма по французскому образцу была введена также в армии и гвардии. В обществе это встретило неудовольствие, поскольку момент для таких перемен был явно неподходящим.
Накануне выступления 26 августа 1855 года в Царском Селе на Софийской площади состоялся смотр стрелкового полка в присутствии Александра II.
Царя приветствовали пением полкового гимна, получившего название «Слава». Однополчане поговаривали, что А. К. Толстого ждёт венец Жуковского — автора «Певца во стане русских воинов».
По пути А. К. Толстой написал короткое стихотворение, вызванное действительным случаем, произошедшим в Севастополе:
Полку надлежало занять оборону вблизи Одессы на побережье Чёрного моря. Штаб расположился в деревне Севериновке, а первый батальон — в болгарском селе Катаржи (таких сёл около Одессы было несколько).
В военных действиях полк не участвовал, но, тем не менее, нёс огромные потери. Эпидемии оказались страшнее неприятельских пуль. А. К. Толстой — Софье Андреевне Миллер 20 декабря 1855 года: «Везде тиф, диссентерия, у нас нет докторов. Оба наших — один из которых, Сидоров, болен — находятся в Севериновке со штабом; больных перевозят туда то на волах, то на лошадях; у нас нет госпиталя, больные размешены по избам — один на другом, умирают лицом к лицу; места совсем нет; выздоравливающие разбросаны по всей Севериновке, и присмотру за ними никакого нет; они часто убегают, едят вредные вещи у хозяев и опять заболевают. Вчера третья рота перевозила своих больных через наше село; один из них скончался в дороге, и я принял его тело в мой домик. Я хотел оставить его на всю ночь, но нашли возможность отвести для него пустую землянку… Сегодня я возил туда священника и присутствовал на панихиде. Какие хорошие люди болгары, гостеприимные, добродушные; они одеты точно люди на картинах Каналетто — курящие трубки на площади св. Марка. Во всяком доме находятся образа православные… Они ненавидят турков, от которых бежали, и говорят библейским славянским языком».
В январе следующего года А. К. Толстой съездил в Одессу. Вот его впечатления (письмо Софье Андреевне Миллер от 16 января 1856 года):