В мае 1945 года Государственный джаз-оркестр РСФСР выступал с новой программой. Всё в этой новой программе было хорошо, но руководитель оркестра Леонид Утёсов чувствовал, что всё-таки не хватает песни, которую можно было бы считать заглавной.

И вот однажды аккордеонист оркестра Аркадий Островский нашёл подходящее стихотворение. Если положить его на музыку, то может получиться та самая песня, которой так не хватало новой программе коллектива. Утёсов вспоминает:

«Не припомню, в какой из центральных газет нашёл Аркадий стихотворение Сергея Михалкова, но когда прочитал мне его, я сразу понял: это именно то, что мы давно искали, и чего так недоставало программе, с которой выступали в незабываемые победные майские дни.

Аркадий загорелся идеей сочинить песню. Он созвонился с Сергеем Владимировичем, и вскоре оба они нагрянули ко мне домой и дружным дуэтом попытались спеть то, что у них получилось.

Слушать их было, прямо скажу вам, уморительно. У Аркадия - голоса никакого, а Михалков заикается, правда, немного меньше, чем когда говорит. Но сколько души и страсти вложили они в показ этого первого своего совместного песенного детища, что я дослушал их до конца. И попросил срочно инструментовать песню, а через несколько дней она уже исполнялась мною в концертах».

Долгое время считалось, что песня «Сторонка родная» родилась хотя и в мае 1945 года, но уже после окончания войны. Но вот журналист-фронтовик И. Мокрецов, сотрудник газеты «Красное знамя», опубликовал свой очерк «Горячие строки», в котором есть такое свидетельство:

«Прожили мы в Вене неделю... Когда выпадал часок-другой посвободнее, ходили по улицам и площадям, присматривались к народу, побывали в безлюдном парламенте, у руин Венской оперы на Имперском мосту.

У подъезда одного дома однажды мы увидели группу бойцов. В центре сидел баянист и подбирал какую-то мелодию. Перед его глазами товарищ держал газету, в которую заглядывали и остальные. Это был свежий номер «Красного знамени». Чем же наша газета их заинтересовала?

Я заглянул и сразу же вспомнил одно событие в жизни нашей редакции. В ту пору в 4-й гвардейской армии находились писатели П. Павленко и С. Михалков. На встречу с ними в политотдел ездили редактор Еремей Семёнович Меликадзе и секретарь Илья Владимирович Аргинский. Они и сообщили, что Сергей Михалков написал в Вене песню «Сторонка родная».

Армейская газета поместила песню в номере за 20 апреля 1945 года. Её и старались теперь разучить солдаты».

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

К сказанному остаётся лишь добавить, что песня «Сторонка родная» имела следующее посвящение: «Посвящается гвардейцам войск генерал-лейтенанта Захватаева».

Эта песня родилась в знаменательный день - 9 мая 1945 года. Поэт и военный корреспондент Цезарь Солодарь в ночь с 8 на 9 мая присутствовал на историческом событии — подписании гитлеровским фельдмаршалом Кейтелем акта о безоговорочной капитуляции фашистской Германии. Утром он уехал по разрушенным улицам Берлина на аэродром и по дороге стал свидетелем эпизода, который и лёг в основу песни.

На оживлённом перекрёстке стояла девушка в солдатской шинели, с флажком в руке и властно регулировала движение. Тогда на берлинских перекрёстках было много молодых советских девушек-регулировщиц. Экраны кинотеатров всего мира обошли кадры документальной хроники, на которых была запечатлена одна из таких регулировщиц - Лидия Овчаренко из украинского города Сталино (Донецка).

К перекрёстку приближалась конная колонна, возглавляемая казаком в кубанке. Регулировщица движением флажка остановила поток машин и, улыбнувшись казаку, крикнула: «Давай, конница, не задерживай!».

Утром Солодарь улетал в Москву. В самолёте, под впечатлением этого мимолётного, но символического эпизода, он написал в своём блокноте: «По берлинской мостовой кони шли на водопой...» и далее, почти что не задумываясь, в поэтической форме описал увиденное.

В Москве он сразу же отправился к композиторам братьям Покрасс, известными своей склонностью к «кавалерийской» тематике и показал им своё сочинение.