При таком изначальном наименовании неудивительно, что Данелия долго противился рекомендациям Шпаликова взять на главную роль — метростроевца Коли — Никиту Михалкова, с чьим старшим братом Андроном Геннадий близко дружил. В то время, пока сценарий писался, Никита никак не тянул на верзилу. Но когда после долгих мытарств сочинения Шпаликова — Данелии по инстанциям (что было связано с одиозным статусом все той же «Заставы Ильича») картину наконец запустили в производство, Геннадий привел Никиту на площадку, и Георгий Николаевич немедленно утвердил последнего на центральную роль. К тому времени младший Михалков уже вымахал именно в такого верзилу, каким его знает весь советский и постсоветский народ.

Вспоминая о роли, впервые принесшей ему всесоюзный успех, Михалков по сей день жмурится от удовольствия:

«Съемки „Я шагаю по Москве“ — это была песня.

Данелия — молодой, веселый, легкий. Мне очень повезло, что первая большая актерская роль, первая главная роль была в фильме, который снимал именно он. Данелия работал шутя, играя, не надувая щек. Я был совсем молодой и так ощутил атмосферу тех съемок… Тогда впервые понял, что хочу этим заниматься. И тогда уже начинал что-то предлагать для своей роли. Я сам придумал, что мой герой к герою Стеблова выйдет с лисьей маской на лице. Чтобы это было неожиданно. Данелия сразу сказал: „Можешь попробовать“, а потом, через паузу: „Э-э, брат, да я дам тебе рекомендацию во ВГИК на режиссерский“. И дал, но не сразу. Я тогда учился в „Щуке“, во ВГИК пошел позже».

В той же «Щуке» (Театральном училище им. Б. В. Щукина) был найден исполнитель самой комической роли в фильме — Саши, лучшего друга Коли — Евгений Стеблов, ранее снимавшийся только в массовке. Ну а более старшие Локтев и Польских ко времени съемок у Данелии могли уже считаться звездами: первый исполнил главную роль в картине Якова Сегеля «Прощайте, голуби!», вторая — знаменитую «Дикую собаку Динго» в фильме Юлия Карасика.

«С Георгием Данелия у актеров сразу установился творческий контакт, мы понимали его с полуслова, — свидетельствует Михалков. — Он требовал от нас предельной искренности и добивался этого порой самым неожиданным образом. Снималась комедийная сцена в парке. По сюжету мы должны были смеяться весело, отчаянно, до слез. Испробовали всё — ничего не получалось. И тогда наш режиссер, опустившись на четвереньки, как-то боком, чрезвычайно быстро пополз к кустам. Мгновение стояла мертвая тишина, а потом грянул оглушительный смех. Оператор Вадим Юсов спешил заснять нужные кадры. Эта сцена получилась очень живой в фильме.

Интересно снимал Данелия сцены в ГУМе. Толпы любопытных собирались вокруг нас, как только начинали устанавливать свет. Тогда принесли запасную камеру и в дальнем углу магазина инсценировали съемку. Этот „обманный маневр“ сделал свое дело: нужная нам площадка мгновенно опустела, и мы могли спокойно работать перед камерой, скрытой от посторонних глаз на втором этаже. Люди не замечали, что идет съемка, они не замечали, что были ее участниками, и вели себя как обычно: подходили к прилавкам, разговаривали, рассматривали товары и так далее. Это позволило и нам чувствовать себя перед камерой легко и свободно».

Легкость и свобода — определяющие понятия для «Я шагаю по Москве». Все, кто работал над фильмом, отмечали впоследствии эту неслыханно раскованную атмосферу, в которой проходили съемки. Совершеннейшей непринужденностью, естественностью в результате оказался пропитан и каждый кадр картины.

Для Данелии в то время существовало три авторитета, мнением которых он дорожил необычайно, — его отец Николай Дмитриевич, его учитель Михаил Ильич Ромм и его друг Сергей Бондарчук.