Старухину повезло, что в 1971 году донецкий «Шахтер» вылетел из высшей лиги в первую и в играх против него на забивного нападающего обратил внимание тренер шахтеров Олег Базилевич. По словам последнего: «Я внимательно следил за Старухиным и представлял обновленный «Шахтер» именно с таким нападающим».

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

Однако в Донецке Старухин оказался с большими приключениями, поскольку руководство «Строителя» не хотело его отпускать. В итоге игрока буквально выкрали из Полтавы, как цыгане крадут невест. Вот как сам Старухин рассказывал об этом: «Готовимся мы к очередной игре, ночуем на базе в дачных дощатых домиках на берегу Ворсклы. Часа в три ночи — стук в окошко. Выглянул: какой-то незнакомый мужик жестами показывает — дескать, выйди, разговор есть. Потом второй незнакомец в окошке нарисовался (это был Алексей Дрозденко. — Авт.)… А уж когда там Лариса, жена, появилась, совсем обалдел, подумал, что все еще сплю. Люди из «Шахтера» хитро все обставили: сначала заехали за Лоркой моей в Полтаву, ее уговорили-умаслили, ну а мне-то уж и отступать вроде некуда. Чтобы никого из спящих ребят не разбудить, побросал в темноте на ощупь в сумку бутсы, спортивный костюм — и деру! Никогда не подозревал, что рафик — такой скоростной автомобиль, каким он мне показался в ту ночь. Главным было уйти за пределы Полтавской области, пока тревогу не подняли и погоню не организовали. Обошлось…»

Когда на следующее утро пропажа Старухина обнаружилась, полтавское руководство подняло на уши Федерацию футбола СССР. И она выпустила приказ, запрещавший беглецу выступать за «Шахтер», который в тот год (1972) успешно боролся за возвращение в высшую лигу. Тогда боссы «Шахтера» пошли на хитрость. Они стали выпускать Старухина в дублирующем составе под чужой фамилией — Черных (свой первый матч наш герой сыграл в августе 1972 года: это была товарищеская игра против сборной Кубы, где Старухин отметился голом). Все бы ничего, однако разработчики этой аферы не учли, что протоколы матчей дублеров тоже поступают в Москву, в ту самую Федерацию футбола. И там конечно же быстро обратили внимание на забивного, но никому не известного форварда. Вскоре из столицы пришел вызов: футболист Черных должен прибыть на сбор молодежной команды СССР. Боссы «Шахтера» встали перед дилеммой: что делать? В итоге отправили телеграмму, заверенную врачом: так, мол, и так, но футболист Черных внезапно заболел менингитом и выехать в Москву никак не сможет. После этого донецкие тренеры стали вписывать Старухина в протоколы матчей дублеров под разными фамилиями.

Между тем в 1972 году «Шахтер» добился возвращения в высшую лигу и Старухину было разрешено легализоваться. И он рьяно взялся за дело: в кубковом матче против запорожского «Металлурга» забил два мяча. Затем в первом же матче на открытии сезона (он состоялся 7 апреля 1973 года в Донецке) забил гол спартаковцам (москвичи проиграли 1:2), потом — в Москве — торпедовцам и армейцам. О последнем голе сам Старухин вспоминал следующее: «Толя Коньков приложился к мячу с такой силой, что от груди вратаря армейцев Астаповского он отскочил, как от каменной кладки. А поскольку при этом мяч задел руки голкипера, траектория рикошета получилась очень удобной для меня. Я поймал мяч головой за пределами штрафной площади — и оттуда попал точно в «девятку». Хотя до ворот было метров двадцать!..»

Итак, тот гол армейцам Старухин забил головой. И это не было случайностью — большую часть своих голов он забивал именно этой частью тела, что было редкостью. У Старухина в этом плане был настоящий дар: он так располагался в штрафной площадке противника и так высоко выпрыгивал, что мяч четко приземлялся на его лысину (а шевелюрой он не блистал) и точно летел в незащищенную часть ворот. По словам самого форварда: «Закономерности поведения мяча в воздухе во всех игровых видах спорта примерно одинаковы. Ведь совсем необязательно выше всех прыгать, чтобы обвести блок над сеткой или завладеть отскочившим от щита мячом. Главное — встретиться с ним в нужный момент и в нужной точке пространства, опередив при этом соперника. А уж чем потом сыграть — головой или рукой — принципиального значения не имеет. Когда я окончательно определился с выбором и занимался в футбольной школе, помню, мы зимой даже играли в волейбол… головами. Зальчик был тесный, любой сильный удар ногой мог обернуться разбитым окном, и мы по волейбольным правилам на «раз-два-три» перебрасывали мяч головами с одной стороны площадки на другую. Занятие, между прочим, очень полезное, однако в наших командах мастеров почему-то ничего подобного не практиковалось…»

А вот что напишет о таланте Старухина журналист Ю. Юрис: «Будучи «чистым» центрфорвардом, не обремененным на поле никакими другими обязанностями, кроме «забивных», а значит, зависимым от партнеров, Старухин настолько органично был встроен в игру «Шахтера», что и партнерам жилось возле него очень комфортно. Его знаменитые сбросы мячей, выигранных в воздушных дуэлях, становились сущим проклятием для соперников. Жаль, что в то время учет индивидуальных футбольных заслуг по системе «гол плюс пас» еще не велся, иначе послужной список донецкого форварда получился бы гораздо более впечатляющим. Сам Старухин сброс мяча головой под удар считал даже эффективнее паса ногой, поскольку он не так очевиден для обороняющихся и, как правило, более удобен для бьющего…»

В сезоне-73 «Шахтер» занял 6-е место — очень хорошо для команды, которая только что вернулась в высшую лигу (был повторен результат 1967 года). Ведущими игроками в клубе были ветераны Юрий Дегтерев, Александр Васин, Виктор Звягинцев, Анатолий Коньков, Владимир Сафонов, а также новички Валерий Горбунов и Виталий Старухин.

Одно из первых интервью Старухина в центральной прессе появилось осенью 1974 года. Это была газета «Советский спорт», номер от 2 октября (автор — В. Березовский). Приведем из него отрывок:

«…Помните: в раздевалке, после матча с «Торпедо» в Лужниках, грозились, что вот доиграю сезон — брошу футбол!

— Забудьте те слова. Сгоряча шумел. Футбол невозможно бросить. Тяжелый тогда период был: без Конькова игра не получалась, состав менялся, ссориться начали. Чего не наговоришь, чтобы выговориться…

— Сейчас «Шахтер» поражает своими достижениями. Вы потеряли не только Конькова и Звягинцева, травмированы Ванкевич и Жуков, а команда семь туров не знает поражений, вклинилась в лидирующую группу. Как это объяснить?

— Я бы сказал так: совесть не позволяет плохо играть. Выходим на каждую игру, словно вдесятером, играем, как в песне поется: «за себя и за того парня». Вроде бы молчаливо берем дополнительные обязательства. Не стало диспетчера — все в меру стараются заполнить пробел, помогают друг другу — пошла командная игра.