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

Только что закончилась Сталинградская битва. Но разведданные говорили о том, что к лету 1943 года Вермахт готовит новое наступление в районе Курска. Советское командование начало стягивать туда силы для генерального сражения. Командующий Донским фронтом генерал К.К.Рокоссовский пригласил к себе Евгения Долматовского и Марка Фрадкина, которые как раз находились в районе боёв под Сталинградом, вручил им ордена Красной Звезды и поинтересовался, нет ли у них новых задумок, желательно лирических песен. Дело в том, что, по данным советской разведки, немцы судили о планах советского командования по наполнению радиоэфира. Если советские войска готовили наступление, по радио звучали бодрые марши, а когда затишье, то легкомысленные вальсы. Долматовский вспомнил своё стихотворение, написанное ещё в первую, самую страшную военную зиму. С тех пор он успел побывать в окружении и в немецком плену, дважды бежал, чудом спасся от расстрела. Фрадкин написал вальс, который очень точно попадал в настроение, но ритмически не совпадал с текстом. Стихи пришлось переписать.

В своих воспоминаниях Евгений Долматовский сообщал, что история, описанная в этой песне, была связана с конкретным эпизодом, рассказанным Фрадкину лётчиком Василием Васильевым. Как-то, оказавшись поздно вечером в одной из прифронтовых деревень, Василий услышал звуки музыки. Подойдя поближе, он увидел танцующую молодёжь, а также стоявшую в стороне одинокую девушку. Пригласив её на вальс, лётчик познакомился с ней — её звали Зиной. Но очень скоро им пришлось проститься, поскольку засигналил шофёр машины, на которой должен был уезжать Василий. Рассказав Фрадкину об этой истории, Васильев добавил: «Вот вы, композиторы, песни сочиняете. У меня к вам просьба: напишите песню о том, что я рассказал. Если всё точно опишете, Зина поймёт, что это о нас с ней. Может, она услышит, откликнется вам». И действительно, через некоторое время та девушка написала на радио письмо, в котором она просила узнать адрес лётчика. Фрадкин рассказывал: «Мы связались с авиасоединением, где служил лейтенант. Но Василий Васильев уже не мог ответить Зине: в одном из воздушных боёв он погиб смертью героя…».

Рокоссовскому очень понравилась и музыка, и текст. Генерал сказал авторам: «Мы с вами встретимся на очень важном участке фронта». Позже этот участок стал известен на весь мир как Курская дуга. Долматовский и Фрадкин отправились под Курск. Поезд шёл почти неделю, песня была презентована авторами на нескольких полустанках и когда они приехали, оказалась, что песня их опередила, её уже вовсю пели в войсках.

Первым исполнителем песни был Леонид Утёсов.

Песня «Случайный вальс» в исполнении Леонида Утёсова звучит в фильме Якова Сегеля «Первый день мира» (1959), в фильме Владимира Хотиненко «Зеркало для героя» (1987), а также в фильме Андрея Хржановского «Полторы комнаты, или Сентиментальное путешествие на родину» (2009). Мотив этой песни присутствует в новелле Евгения Цыганова «Случайный вальс» (2010), входящей в цикл короткометражных фильмов «9 мая. Личное отношение».

Эта песня – напоминание о том, что на войне не только совершали подвиги, громили врага, но и любили, верили, ждали. Ждали, когда вернутся домой, обнимут своих родных, все вместе ждали такую желанную Победу!