Песня написана вскоре после окончания Великой Отечественной войны, осенью 1945 года, для театрализованной программы «Весна победная», которую задумал и осуществил к празднику 7 ноября режиссёр Ансамбля песни и пляски войск НКВД Сергей Юткевич. Все песни в ней, по замыслу постановщика, должны были связываться определённой сюжетной канвой — отъезд бойцов домой из Германии, поэтому их темы и характер были заранее намечены и оговорены. Авторам песни — композитору Анатолию Новикову и поэту Льву Ошанину — был вручен длинный их список, отпечатанный на машинке. Из этого списка Новиков и Ошанин выбрали песню-раздумье с условным названием «Под стук колёс» и приступили к работе.