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