Итак, в команду «Спартак» Старшинов был зачислен еще будучи мальчишкой — ему было восемь лет. Однако во взрослую хоккейную команду этого общества его пригласили в сезоне 1957/1958 (это сделал тренер Александр Игумнов). Отметим, что этот уникальный тренер первым в СССР получил звание заслуженного тренера за работу с детьми. И Старшинов, и братья Ярославцевы, а также ряд других игроков, пришедших в то время в «Спартак», были воспитанниками Игумнова.
К тому времени знаменитые братья Майоровы (Борис и Евгений), которые были старше Старшинова на два года, уже играли в основном составе. В звено с ними новичка определил опять же Игумнов. Дебют тройки состоялся 19 октября 1958 года в матче с ЦСКА. Однако ту встречу «Спартак» бездарно проиграл с разгромным счетом 1:13. Говорят, после игры братья Майоровы заявили тренеру, что не хотят играть в одном звене с «этим тихоходом». Хотя сам Старшинов эту историю отрицает. Однако Игумнов вежливо осадил братьев, заметив им, что по одной игре судить о потенциале звена еще рано. Как покажет время, прав оказался именно тренер: вскоре это звено стало одним из самых результативных не только в «Спартаке», но и в советском хоккее.
В своем первом чемпионате СССР (1957/1958) Старшинов сыграл несколько игр, однако голами не отметился. В том сезоне «Спартак» занял 9-е место (45 очков), а лучшим бомбардиром в команде стал Юрий Горбунов, забивший 27 шайб, самым результативным игроком стал армеец Алексей Гурышев, на счету которого было 40 забитых шайб.
В том же 1958 году Старшинов стал студентом. Причем в Московский авиационно-технологический институт (там же учились и братья Майоровы) он поступал еще год назад, но не сумел сдать экзамен по физике. Спустя год попытку повторил, и она оказалась более успешной.
Паралелльно учебе Вячеслав продолжал играть в «Спартаке», который год от года играл все лучше. Так, в сезоне 1958/1959 он занял 5-е место (Старшинов забил 12 шайб), в 1959/1960 — 6-е место (на счету героя нашего рассказа было уже 16 забитых шайб), в 1960/1961 — 6-е (Старшинов снова отметился 16 шайбами, а его партнер по тройке Борис Майоров забил на 4 шайбы больше).
О том, каким образом Старшинов (вместе с братьями Майоровыми) попал в сборную СССР, есть разные версии. Вот как об этом вспоминает сам Старшинов:
«Нашу тройку в 1959 году включили в сборную, которая проводила товарищеские матчи в Швеции с национальной командой. В первой игре мы, по-моему, уступили, но наша тройка забросила все шайбы сборной, а вторую выиграли — 3:2, и опять все голы были нашими. Но на Олимпиаду 1960 года в Скво-Велли нас все равно не взяли: мы же были спартаковцами. Незадолго до Игр вызвал Тарасов и сказал: «Переходите все трое в ЦСКА — и поехали на Олимпиаду». Мы отказались и остались за бортом.
Если бы у меня были хоть какие-то сомнения, конечно перешел бы. Тем более что мой двоюродный брат — военный, генерал-майор авиации. Благодаря его влиянию я и выбрал себе вуз — Авиационно-технологический институт. Дисциплину я очень люблю, но, видимо, родился все же гражданским человеком. Не будем лукавить: многие тогда шли в ЦСКА, потому что там элементарно больше платили. Меня же это никогда не интересовало, так как на первое место всегда ставил творчество. Однако у Тарасова я научился правильно жить. Распорядок дня, дисциплина, ответственность. Пусть он достигал этого посредством давления, но ведь без этого тоже нельзя…»
Однако, согласно статистическим данным, в том предолимпийском турне сборной СССР по Швеции Старшинова и братьев Майоровых не было (видимо, память здесь нашего героя подводит). А вот в следующем году (в январе 1961 года) их действительно взяли в «шведское» турне. В первой игре наши уступили 4:6 и Старшинов в нем отметился одним голом. Во втором матче советские хоккеисты взяли реванш со счетом 3:2, но Старшинов в нем не отметился. А спустя два месяца звено Старшинов — братья Майоровы отправились на свой первый чемпионат мира, который проходил в Лозанне и Женеве в марте 1961 года. На этом турнире советские хоккеисты заняли 3-е место. Однако лучшими бомбардирами турнира стали Борис Майоров, набравший 17 очков (7 забитых шайб и 10 результативных передач), и Вячеслав Старшинов с 9 очками (6 + 3).
Тем временем в сезоне 1961/1962 московский «Спартак» стал чемпионом страны — впервые в своей истории. Он набрал 65 очков, опередив на одно очко своих земляков из «Динамо». Победный состав «Спартака» выглядел следующим образом: вратарь — Анатолий Платов; защитники — Владимир Испольнов, Валерий Кузьмин, Алексей Макаров, Анатолий Рыжов; нападающие — Рауф Булатов, Юрий Глухов, Александр Кузнецов, Игорь Кутаков, Борис Майоров, Евгений Майоров, Вячеслав Старшинов, Валерий Фоменков, Валерий Ярославцев; тренер — Александр Новокрещенов.