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