Далее перед режиссёром встала следующая задача - подбор актёров. Здесь возникла новая проблема. Те, кого Владимир Валентинович хотел бы видеть в главных ролях, наотрез отказывались от этой работы. Одни высказывались о будущем фильме, как о скучной мыльной опере, а другие не хотели сниматься у начинающего режиссёра.
Когда все трудности с актёрским составом наконец-то были решены, и работа над кинолентой шла полным ходом, перед Меньшовым возник новый вопрос: кто украсит фильм созвучной сюжету музыкой? На киностудии ему предлагали композиторов, но режиссёр их отвергал: возможно не мог добиться от сочинителей того, что ему было нужно. Лишь после рекомендации одного из музыкальных редакторов обратиться к барду Сергею Никитину, проблема оказалась решённой. Режиссёр попросил композитора сочинить всего пару песен, одна из которых должна обязательно посвящаться Москве и стать лейтмотивом картины. Вот с этого момента и начинается тоже довольно замысловатая история всенародно любимой песни.
Для сочинения текста композиции Никитин попросил пригласить учёного биолога и талантливого барда Дмитрия Сухарева, на стихи которого создал не одну песню. Поэта сразу познакомили со сценарием и объяснили, что от него хотят. Сухарев не заставил долго ждать результата и через несколько дней предоставил стихи, которые весьма удивили как композитора, так и режиссёра. Дело в том, что в поэтическом тексте упоминалось не имя главной героини, которую звали Екатерина, а её дочери Александры. На вопрос, почему не Катерина, а Александра, Дмитрий Антонович ответил, что таким образом он перебросил мост из прошлого в будущее, а помимо того имя Александра для песни более мелодичное. В конечном итоге стихи поэта были одобрены, а вот музыка у композитора никак не получалась. Сергей сочинял одну версию за другой, однако его жене Татьяне, с которой он должен был исполнять песню в фильме, все эти варианты не нравились. Лишь шестая редакция композиции получилась красивой и романтичной, а самое главное идеально подчёркивающей настрой картины. Впрочем, когда песню стали укладывать на кадры фильма, оказалось, что сочинённых куплетов маловато, то есть необходимо дописать ещё один. И вновь возникла проблема: Сухарев уехал за границу, а режиссёра торопили сроки. Выход из этого сложного положения нашёл Сергей Никитин. За помощью он обратился к своему другу Юрию Визбору. Выдающийся бард без промедления откликнулся на просьбу и не только сочинил недостающий куплет, но и кое-что подправил в тексте Сухарева. Когда Дмитрий Антонович вернулся в Москву и обнаружил, что его творение изрядно отредактировано, он не на шутку рассердился и даже серьёзно обиделся на Визбора. Помирить давних приятелей удалось лишь режиссёру. Меньшов объявил, что в начале фильма будет использована композиция Сухарева, а в заключительных кадрах картины вариант Визбора. После такого решения барды примирились, а их дружба после данного недоразумения стала ещё крепче.
