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