Андрей Петров:
— Мне гораздо легче написать песню, чем рассказать о ней. Скажу только, что рождалась она довольно трудно. Я вспоминаю, что было сделано семь или восемь различных вариантов. А песня эта — о Москве, о юности и о хорошем настроении.

Что же касается текста, заказанного Георгию Шпаликову, то ждать его пришлось довольно долго. Получив аванс, поэт пропал из поля зрения на две недели. Появился он только в день выдачи зарплаты и очень удивился, что Данелия сотоварищи всё ещё на съёмках, а не в ресторане.

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

Как и в случае с «Песней о друге», «Я шагаю по Москве» записал Эдуард Хиль, и в этом исполнении новая песня пошла в эфир ещё до выхода фильма, став своего рода рекламой.

Роскомнадзор: сайт youtube.com нарушает законодательство РФ

В самом же фильме песню спел не Хиль, а исполнитель главной роли — юный Никита Михалков. Певцом актёр не был от слова «совсем», но зато в контексте фильма его голос звучал более естественно и уместно. Спустя почти 20 лет уже маститый Никита Сергеевич повторит этот опыт ещё раз, исполнив в фильме «Жестокий романс» другую песню Петрова — «Мохнатый шмель…».

Песня имела огромный успех и стала «визитной карточкой» и Москвы, и Хиля. Именно благодаря ей певец попал в 1965 году на Международный фестиваль в Сопоте, стал там лауреатом, после чего окончательно обрёл «звёздный» статус на советской эстраде.

Эдуард Хиль:
— В Сопоте я оказался с подачи Андрея Петрова. Когда выдвинули песню из фильма «Я шагаю по Москве», которую я пел еще до выхода фильма, он захотел, чтобы я поехал. Я поехал и получил там звание лауреата, за польскую песню Марка Сарта, которую сам выбрал, и за песню Аркадия Островского о любви.

Георгий Данелия:
— …каково же было мое удивление, когда я увидел по телевизору, что под эту музыку, под которую у меня в фильме шагали Колька, Володя и Саша, по ковровой дорожке мимо почетного караула идут Генеральный секретарь ЦК КПСС Леонид Ильич Брежнев и президент Соединенных Штатов Ричард Никсон…

«Как провожают пароходы» (1965)

На перспективного певца тут же обратили внимание другие композиторы — например, знаменитый Аркадий Островский. Одним из первых шлягеров Островского, написанных специально для Хиля, стала песня «Как провожают пароходы». В её ритмике мне всегда чувствовалось что-то латиноамериканское — то ли румба, то ли танго.

Стихи для песни были найдены композитором в сборнике его друга — поэта Константина Ваншенкина. А вот припев Островскому и Хилю пришлось досочинить самим.

Эдуард Хиль:
— Мне часто звонил из Москвы Аркадий Островский и говорил: «Эдик, надо срочно записать песню. Приезжай завтра». И наигрывал мне песню, скажем, «Как провожают пароходы». А припева в ней нет, просто музыкальный проигрыш. «Ты приедешь, мы что-нибудь придумаем», — сказал Островский. И мы уже вместе ввели припев: «Вода, вода, кругом вода…»

Говорят, самому поэту нововведение не понравилось…

Михаил Островский (сын композитора):
— …в Центральном доме литераторов на творческом вечере Ваншенкину кто-то из коллег сказал: «Вы такой хороший поэт, но что это за строчки «Вода, вода, кругом вода»? Константин Ваншенкин встал и сказал: «Стихи мои, а «вода, вода» — Островского».

Дмитрий Хиль (сын певца):
— …Ваншенкин, услышав такую вольность, сначала возмущался, но когда получил первые гонорары и признание коллег — быстренько смирился.

А вот Владимиру Высоцкому бессмысленным казался не только припев, но и весь текст песни.

Владимир Высоцкий (реплика на концерте 30 апреля 1979 года):
— …Или там нечто глубокомысленное, вроде «Провожают пароходы совсем не так, как поезда…». Я было сначала думал, что за этим что-то есть, нет, действительно, просто не так, пароходы не так, как поезда, а самолёты не так, как пароходы, а автомобили и автобусы не так, как самолёты. Ну и что? Да разве в этом дело?

Впрочем, обычные слушатели не копали так глубоко и сразу поняли — поэт имеет в виду, что проводы пароходов, уходящих в синюю морскую даль, выглядят романтичнее, чем проводы поездов. Не случайно со временем суда стали отправляться в плаванье под звуки именно этой песни.