Летом того же года в Москве состоялась Спартакиада народов СССР. Стрельцов и Иванов были приглашены играть за сборную Москвы. Играли они хорошо, получили свои первые в жизни золотые медали и вошли в список 33 лучших игроков Спартакиады. А затем осенью их взяли в сборную СССР для участия в Олимпиаде, которая состоялась в Мельбурне, где их ожидал новый триумф.

В первой же игре со сборной ФРГ наши победили 2:1. Второй гол в ворота немцев забил Стрельцов. Затем была победа над сборной Индонезии – 4:0. В полуфинале наши встречались со сборной Болгарии. Тот матч был одним из самых трудных и драматичных для нашей сборной. При счете 1:0 в пользу болгар у нас внезапно получили травмы сразу два игрока: В. Иванов и Н. Тищенко (у последнего была сломана ключица). И хотя с поля они не ушли, однако игра у нашей команды никак не получалась. До конца матча остается всего 8 минут, и болгары мысленно уже торжествовали победу. И тут случилось чудо. Травмированный Тищенко, получив мяч, точным ударом отправляет его в ноги Стрельцову. Тот совершает стремительный рывок от центра поля и мощным ударом вгоняет мяч в сетку ворот болгарской команды. 1:1. А буквально через несколько минут после этого Борис Татушин забивает и второй гол. Победа!

В финале олимпийского турнира наша сборная играла с командой Югославии. К сожалению, Стрельцов в этом матче на поле так и не вышел. Почему? Получивший травму в предыдущем матче, Иванов на поле выйти также не смог, и поэтому тренер Игорь Нетто решил не выпускать на поле и его торпедовского напарника – Стрельцова. Вместо них в нападении играл спартаковский тандем Татушин – Исаев. В центре играл их же коллега по команде Никита Симонян.

Югославская сборная считалась тогда одной из сильнейших в мире. На предыдущей Олимпиаде в Хельсинки (1952) она завоевала золотые медали в драматичной борьбе, обыграв нашу сборную во второй игре. То же самое она попыталась сделать и на этот раз. И ей наверняка удалось бы это сделать, не стой в наших воротах Лев Яшин. Отразив более пятнадцати опасных ударов югославов с разных точек поля, наш прославленный голкипер сумел внести смятение в ряды противника. Этим и воспользовались наши нападающие. В один из моментов, когда шла 50-я минута матча, Анатолий Ильин вогнал мяч в ворота сборной Югославии. Этот гол стал золотым, и наша сборная стала олимпийским чемпионом. Правда, Стрельцову золотую медаль не вручили, так как в последней игре он не участвовал. Но когда команда вернулась на родину, никого из футболистов не забыли – всех наградили орденами. Стрельцов и Иванов получили ордена «Знак Почета».

Год 1957-й еще более укрепил положение Стрельцова в советском футболе. В том году его родное «Торпедо» заняло в чемпионате страны 2-е место (первое взяли динамовцы Москвы). Стрельцов забил в том чемпионате 12 голов.

Каким был Стрельцов за пределами футбольного поля? К моменту, когда на него обрушилась всенародная слава, ему было всего лишь 19 лет. Мало кто из его сверстников смог бы устоять от соблазнов, которые открывает перед ними такая популярность. Не стал исключением и наш герой. Когда он впервые перешагнул порог команды «Торпедо», на нем был старенький ватник, а в руке деревянный чемодан. К 1957 году он получил от команды отдельную квартиру в новом доме на Автозаводской улице, стал прилично зарабатывать, женился (в этом браке у него родилась дочь). Одевался Стрельцов стильно, на голове соорудил модный кок. В общем, пижонил. Футболисты в те годы считались популярными личностями, многие из них были вхожи в артистическую богему. По словам самого Стрельцова, его никогда не тянуло в эту компанию, хотя со многими популярными артистами он был знаком (например, с Петром Алейниковым, Владимиром Земляникиным, Анатолием Папановым и др.).

Как утверждают очевидцы, команда «Торпедо» в 50-е годы не отличалась большой внутренней дисциплиной.