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