Мастерство молодого вратаря растет и вот, уже с 1936 года, он основной вратарь днепропетровского «Спартака».
После победы в 1937 году в чемпионате Украины, игроки команды попали под пристальное внимание руководителей других команд из других городов. Но молодой перспективный вратарь Алексей Леонов особенно обратил на себя внимание еще после того, как наши днепропетровские спартаковцы во всесоюзном турнире команд этого общества, заняли 2-е место, уступив только маститым москвичам в 1936 году.
В разных источниках, по-разному, трактуется факт появления Алексея Леонтьева в московском «Спартаке».
По одним, после неудач днепропетровского «Спартака» в 1939 году, передачи части его игроков в нашу «Сталь», а также ухода части их в армию, он, после долгих колебаний, принял приглашение донецкого /тогда города Юзовка/ «Стахановца». Но он не задержался в этой команде, далее его путь пролег в Москву.
Вот как описывал в 1969 году, его тогдашний отъезд в далеком 1939 году в Юзовку /теперешний Донецк/, и его прощание в редакции газеты «Большевистская смена», наш днепропетровский футбольный историк и журналист Михаил Вольнов: «Приехал уже поздно вечером в редакцию попрощаться.
„Поеду, посмотрю, но, наверное, вернусь“ - сказал он. А на следующий день позвонил Виктор Михайлович Каминский /тренер нашего „Спартака“ - примечание автора/: „Нет ли у Вас Леши, или, может, вы знаете, где его искать. Прибыла телеграмма из Москвы от Николая Петровича Старостина /одного из многолетних руководителей московского „Спартака“ и известного футболиста – примечание автора книги/. Он приглашает Леонтьева в „Спартак“. Мы в тот же день дали знать Алексею о телеграмме, и он отправился в Москву…“.»
Немного, иначе, этот эпизод звучит в воспоминаниях самого Н.П. Старостина: