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