В феврале 1853 года русский посол в Стамбуле А. С. Меншиков ультимативно потребовал особого положения для православных подданных султана. Турки отвергли ультиматум. Вскоре в Дарданеллы вошла соединённая англо-французская эскадра с экспедиционным контингентом на борту. В ответ Россия ввела войска в Молдавию и Валахию. 4 октября 1853 года Турция объявила России войну.

Сначала боевые действия были успешными. 18 ноября 1853 года в Синопской бухте Нахимов уничтожил основные силы турецкого черноморского флота. Но уже в декабре англо-французская эскадра вошла в Чёрное море. Обе державы заявили, что Россия должна очистить Дунайские княжества. Правительство Николая I разорвало отношения с Англией и Францией и в середине марта 1854 года объявило им войну.

Новое военное столкновение России и Европы наконец-то состоялось. Как будто вновь грозило вторжение двунадесяти языков. В конце концов ареной боевых действий стал Крым, но первое время казалось, что война развернётся повсеместно. Английская эскадра подошла к Кронштадту, и петербуржцы могли видеть неприятельские корабли с побережья Финского залива. Над столицей империи нависла опасность. Хотя внешне никаких приготовлений к обороне Петербурга не наблюдалось, но обитатели были настороже.

В эти тревожные дни А. К. Толстой ощутил себя человеком дела. Он со своим приятелем Алексеем Бобринским (в будущем министром путей сообщения) придумал дерзкий план: в случае высадки английского десанта создать партизанский отряд численностью 40 человек. Для такого предприятия предполагалось использовать их членство в Петербургском яхт-клубе, где А. К. Толстой состоял с 1848 года. Он писал Софье Андреевне Миллер 20 июня 1854 года: «…Решено, что я еду в шхеры; я заказал 40 карабинов, по 20 рублей каждый, и уезжаю как можно скорее, но не ранее трёх недель, а если ранее, то лишь временно и для набора людей. Всё делается под предлогом прогулки на яхте и без всякого другого разрешения, кроме как плавать в шхерах. С первым успехом, если таковой будет, мы испросим полномочия на партизанские действия…» Друзья целыми днями бегали по оружейникам.

Англичане вели себя неопределённо; эскадра то отходила от Кронштадта, то вновь возвращалась. Атака на крепость ожидалась 25 июня, в день рождения Николая I, но этого не случилось. Вот отрывок из очередного письма Алексея Толстого Софье Андреевне Миллер от 19 июля 1854 года: «…Вид англичан меня ободрил; я их видел сегодня утром — я был верст 15 за Ораниенбаумом, на Большой горе, откуда их было видно отлично; я насчитал 31 судно. Шувалов и Арнольди, конногвардейцы, которые были со мной, насчитали 33. Англичане всякий день делают десанты от 20 до 50 человек — на неохраняемых берегах. Большею частью они себя хорошо ведут, но иные действуют отвратительно, подобно диким…»

Со временем Толстой и Бобринский решили усложнить свой план. Они задумали приобрести судно, набрать команду из волонтёров и под флагом яхт-клуба вести каперскую войну против английского торгового флота. Поскольку такая война запрещалась международными соглашениями, понятно, что это было крайне рискованное предприятие. К счастью, оно не осуществилось: то ли корабля не нашлось, то ли план стал известен слишком многим. Да и английская эскадра ушла из Финского залива.

Крымская война оставила по себе печальную память. Её принято считать национальным позором России. Но такой болезненный синдром объясняется прежде всего тем, что на протяжении полутора веков Россия шла от победы к победе. 1812 год затмил в памяти бесславие Аустерлица. Однако постепенно николаевская империя стала превращаться в колосс на глиняных ногах. Повсеместно царил экономический застой. Крепостное право не позволяло промышленности черпать рабочую силу из крестьянства и сковывало её развитие. Ужасное состояние российских дорог привело к тому, что в Крым, где сосредоточена русская армия, по сути дела не было ни подвоза оружия и боеприпасов, ни подхода подкреплений. Снаряды везли на волах; предполагалось, что они за день пройдут не менее 50 вёрст, а они делали едва 20, да и то в лучшем случае. Положение было таково, что согласно секретному приказу в Севастополе на 50 вражеских выстрелов отвечали только пятью.

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

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

Из Медведя Алексей Константинович Толстой писал Софье Андреевне Миллер 23 мая 1855 года:

«Я изменяю своему характеру: я, который нуждаюсь в одиночестве, провожу всю жизнь с товарищами. Когда я не на учении, я у них или они у меня. Мы играем в городки, гуляем… Есть между ними занимающиеся литературой и декламирующие неизданные стихи графини Ростопчиной. Я предложил прочесть им свои стихи, и они имели большой успех…

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

Для своего полка А. К. Толстой написал своего рода полковой гимн: стилизованную под народную «стрелковую песню»:

Известно, что А. К. Толстой написал несколько так называемых «военных песен», но до нас, кроме вышеприведённой, дошла ещё только одна: