Со временем Толстой и Бобринский решили усложнить свой план. Они задумали приобрести судно, набрать команду из волонтёров и под флагом яхт-клуба вести каперскую войну против английского торгового флота. Поскольку такая война запрещалась международными соглашениями, понятно, что это было крайне рискованное предприятие. К счастью, оно не осуществилось: то ли корабля не нашлось, то ли план стал известен слишком многим. Да и английская эскадра ушла из Финского залива.
Крымская война оставила по себе печальную память. Её принято считать национальным позором России. Но такой болезненный синдром объясняется прежде всего тем, что на протяжении полутора веков Россия шла от победы к победе. 1812 год затмил в памяти бесславие Аустерлица. Однако постепенно николаевская империя стала превращаться в колосс на глиняных ногах. Повсеместно царил экономический застой. Крепостное право не позволяло промышленности черпать рабочую силу из крестьянства и сковывало её развитие. Ужасное состояние российских дорог привело к тому, что в Крым, где сосредоточена русская армия, по сути дела не было ни подвоза оружия и боеприпасов, ни подхода подкреплений. Снаряды везли на волах; предполагалось, что они за день пройдут не менее 50 вёрст, а они делали едва 20, да и то в лучшем случае. Положение было таково, что согласно секретному приказу в Севастополе на 50 вражеских выстрелов отвечали только пятью.
Но пока что положение не казалось столь уж мрачным. Русское общество было охвачено патриотическим воодушевлением. Севастополь героически оборонялся, и А. К. Толстой решил ехать в Крым. Его дядя, министр уделов Лев Перовский, написал Николаю 1 письмо с предложением создать из государственных крестьян стрелковый полк императорской фамилии. В этот полк набирались добровольцы, но прежде всего меткие стрелки и охотники, ходившие в одиночку на медведя. Русские богатыри приезжали не только из северных и центральных губерний, но и из далёкой Сибири. Царь на письме Льва Перовского наложил резолюцию «Быть по сему». Стрелки получили не обычные гладкоствольные ружья, а штуцера с нарезным стволом. Им даже было положено жалованье три рубля серебром в месяц.
По ходатайству Льва Перовского Алексей Толстой был зачислен в этот полк в чине майора как командир роты. Его однополчанами были Алексей Бобринский и двоюродный брат Владимир Жемчужников. Сборным пунктом первого батальона, в состав которого входила рота А. К. Толстого, стало новгородское село Медведь, где ранее располагалось одно из упразднённых к тому времени аракчеевских военных поселений. Командиром батальона назначен подполковник Даниил Ефимович Жуков.
Из Медведя Алексей Константинович Толстой писал Софье Андреевне Миллер 23 мая 1855 года:
«Я изменяю своему характеру: я, который нуждаюсь в одиночестве, провожу всю жизнь с товарищами. Когда я не на учении, я у них или они у меня. Мы играем в городки, гуляем… Есть между ними занимающиеся литературой и декламирующие неизданные стихи графини Ростопчиной. Я предложил прочесть им свои стихи, и они имели большой успех…
Твой портрет передо мной, и перед ним букет ландышей и лесного жасмина, который я сорвал вчера в Княжем Дворе, где мы были все вместе. Это — великолепное место; нужно пройти две реки, чтоб туда попасть; там дворец и огромный парк; там много ландышей, что совестно ходить. Я не знаю полковника Жукова, который приехал сегодня; говорят, что он — хороший человек. Сипягин — хороший, добрый, благородный малый, который обожает свою роту и чрезвычайно ею любим. Он за солдатами смотрит, как за своими детьми, и каждый день ходит в больницу. Есть офицер из армии, Дубский, лицо которого тебе очень понравится, добрый малый, очень скромный, очень изящный и русский по наружности, впрочем, более малоросс, чем русский… Есть также добрый и хороший малый Кулешёв; ему около 40 лет, высокий, седой и чёрный; я его полюбил с первого взгляда… Впрочем, все офицеры, кроме одного, мне нравятся. Все живут в дружбе и все имеют отвращение к телесному наказанию».
Для своего полка А. К. Толстой написал своего рода полковой гимн: стилизованную под народную «стрелковую песню»:
Слава на небе солнцу высокому!
Слава!
На земле государю великому,
Слава!
Слава на небе светлым звездам,
Слава!
На земле государевым стрелкам,
Слава!
Чтобы рука их была всегда тверда,
Слава!
Око быстрее, светлей соколиного,
Слава!
Чтобы привёл Бог за матушку Русь постоять,
Слава!
Наших врагов за рубеж провожать,
Слава!
Чтобы нам дума была лишь о родине,
Слава!
Ину же печаль мы закинем за синюю даль,
Слава!
Чтобы не было, опричь Руси, царства сильней,
Слава!
Нашего ласкова государя добрей,
Слава!
Чтобы не было русского слова крепчей,
Слава!
Чтобы не было русской славы громчей.
Слава!
Чтобы не было русской песни звучней,
Слава!
Да чтоб не было царских стрелков удалей,
Слава!
Известно, что А. К. Толстой написал несколько так называемых «военных песен», но до нас, кроме вышеприведённой, дошла ещё только одна:
Уж как молодцы пируют
Вкруг дубового стола;
Их кафтаны напаспашку,
Их беседа весела.
По столу-то ходят чарки,
Золочёные звенят;
Что же чарки говорят?
Вот что чарки говорят:
Нет! нет!
Не бывать,
Не бывать тому,
Чтобы мог француз
Нашу Русь завоевать!
Нет!
Николай I умер 18 марта 1855 года. Севастополь был сдан 27 августа 1855 года, когда французские войска овладели господствующим над городом Малаховым курганом. Лишь к этому времени формирование полка наконец-то закончилось. Офицеры и стрелки были одеты в невиданную ранее форму: красные рубахи, полукафтаны, широкие штаны, меховые шапки. По преданию, они были пошиты по эскизам Алексея Толстого и Владимира Жемчужникова. Новый император Александр II, не раздумывая, утвердил инициативу своего любимца. В таком виде полк выступил в поход через Москву на Одессу. Новая форма по французскому образцу была введена также в армии и гвардии. В обществе это встретило неудовольствие, поскольку момент для таких перемен был явно неподходящим.
Накануне выступления 26 августа 1855 года в Царском Селе на Софийской площади состоялся смотр стрелкового полка в присутствии Александра II.
