Предшественниками «Локомотива», основанного в 1936 году, были клубы КОР (1923-1930) и «Казанка» (1931-1935). Еще в 1927-м и 1928-м КОР провел международные матчи с рабочими командами Норвегии и Англии. А создание «Локомотива» совпало с началом проведения чемпионата СССР среди клубов, и железнодорожники участвовали во всех довоенных турнирах высшего дивизиона.

«Локомотив» сразу набрал скорость, постоянно входил в группу ведущих команд страны, а к тому же стал первым обладателем Кубка СССР, выиграв в финале (2:0) у тбилисского (тогда тифлисского) «Динамо». Тренировал  железнодорожников Алексей Иванович Столяров, вскоре ставший заслуженным мастером спорта.

Проблемы у команды возникли после войны, когда она оказалась на последнем месте в чемпионате 1945 года. К слову, спустя год такое же место заняло киевское «Динамо», но, в отличие от «Локомотива», эту команду оставили в группе сильнейших. А железнодорожники вернули себе место в ней лишь в 1948-м. И впоследствии «Локомотив», образно говоря, двигался на разных скоростях, периодически выбывая из высшей лиги, а затем возвращаясь в класс сильнейших. Кубок СССР команда выиграла еще один раз (1957), когда ее тренировал Борис Андреевич Аркадьев. А ее лучшим достижением в чемпионате страны стало второе место (1959), добытое под руководством Евгения Ивановича Елисеева.

С помощью многих ведущих тренеров страны «Локомотив» периодически «набирал скорость». В разные годы с командой работали Гавриил Дмитриевич Качалин, Николай Петрович Морозов, Константин Иванович Бесков, Валентин Борисович Бубукин, Виктор Семенович Марьенко. Но в союзном чемпионате она все равно оставалась лишь пятой среди московских команд. Зато в чемпионате России «Локомотив», благодаря многолетнему плодотворному труду Юрия Павловича Семина, установившего
безусловный российский рекорд по продолжительности работы в одной команде, стал одним из лучших клубов страны.

Становлению «Локомотива» за долгие годы способствовали многие яркие мастера, которые порой добивались больших успехов, выступая и в других командах.

Николай Разумовский. Вратарь. Играл в «Локомотиве» во всех довоенных чемпионатах и в 1947 году. Обладатель Кубка СССР (1936). Начинал играть в «Казанке», выступал также в «Торпедо» (1945-1946). Был начальником команды и председателем ЦС «Локомотива», На протяжении многих лет работал директором стадиона «Лужники».

Валентин Гранаткин. Вратарь. Заслуженный мастер спорта. Чемпион СССР (1932) в составе сборной Москвы, Выступал за сборную СССР, а в «Локомотиве» играл во всех довоенных чемпионатах страны. Впоследствии был председателем Федерации футбола страны и первым вице-президентом ФИФА.

Владимир Мошкаркин. Полузащитник и защитник. Заслуженный мастер спорта. Начинал играть в «Казанке», а затем выступал за «Локомотив» и «Торпедо». Был капитаном «Локомотива», бронзовым призером чемпионата (1945) в составе «Торпедо». Затем был главным тренером «Торпедо», начальником команды в сборной СССР на Олимпиаде (1956) и чемпионате мира (1958), заместителем председателя Федерации футбола страны.

Александр Прохоров. Полузащитник и защитник. Воспитанник «Локомотива», выступал за команду в двух довоенных сезонах. После войны играл в ЦДКА и ВВС. Двукратный чемпион СССР и обладатель Кубка в составе армейцев.

Иван Станкевич. Защитник. Заслуженный мастер спорта. Четыре довоенных сезона провел в «Локомотиве», а затем играл в «Динамо», где стал двукратным чемпионом СССР и участвовал в триумфальном турне по Великобритании.

Виктор Лахонин. Нападающий и полузащитник. Заслуженный мастер спорта, заслуженный тренер РСФСР. Десять сезонов (до войны и после) провел в «Локомотиве», два года (до войны) играл в минском «Динамо». Много лет работал в знаменитой московской ФШМ, возглавлял молодежную сборную РСФСР.

Виктор Лавров. Нападающий. Играл за КОР, «Казанку» и пять довоенных лет за «Локомотив». Обладатель Кубка СССР (1936). Забил первый гол в клубном чемпионате страны (22 мая 1936 года в ворота ленинградского «Динамо»).

Петр Теренков. Нападающий. Заслуженный тренер РСФСР. Играл за «Локомотив» во всех довоенных чемпионатах страны. Обладатель Кубка СССР (1936). На протяжении многих лет тренировал юношеские команды «Локомотива».

Алексей Соколов. Нападающий. Заслуженный мастер спорта. Первые три чемпионата страны провел в «Локомотиве», выиграв с командой Кубок СССР (1936). Затем перешел в «Спартак», где стал двукратным чемпионом страны и четыре раза выигрывал Кубок.

Николай Ильин. Нападающий, полузащитник, защитник. Заслуженный мастер спорта. Чемпион СССР (1935) в составе сборной Москвы. Довоенные чемпионаты страны провел в «Локомотиве», после войны играл в «Торпедо». Был капитаном обеих команд. Обладатель Кубка СССР (1936), финалист Кубка (1947).

Иван Андреев. Защитник. Обладатель Кубка СССР (1936). В чемпионатах страны выступал только за «Локомотив», был капитаном команды. Работал тренером клубных команд «Локомотива».

Василий Панфилов. Нападающий. Заслуженный мастер спорта. До войны играл в минских «Динамо» и «Спартаке», после войны – в московских «Торпедо» и «Локомотиве». Бронзовый призер чемпионата страны (1945) и финалист Кубка (1947). Был тренером «Локомотива» в течение пяти сезонов, много лет работал в детско-юношеской школе клуба.

Валентин Бубукин. Нападающий. Заслуженный мастер спорта, заслуженный тренер РСФСР. Обладатель Кубка Европы (1960). Одиннадцать сезонов провел в «Локомотиве», один – в ЦСКА. Серебряный призер чемпионата страны (1959) и обладатель Кубка (1957). Рекордсмен «Локомотива» по количеству матчей в союзных чемпионатах. Был капитаном сборной СССР.

Виталий Артемьев. Полузащитник. Заслуженный тренер РСФСР. Два года выступал за ВВС, а затем десять сезонов провел в «Локомотиве», был капитаном команды. Завершал карьеру игрока в ярославском «Шиннике». Серебряный призер чемпионата страны (1959), обладатель Кубка (1957). Работал зам. начальника Управления футбола Спорткомитета СССР, старшим тренером и директором школы «Локомотива», председателем МГС «Локомотива».

_{Локомотив»-1955. Слева направо: Евгений Рогов (капитан команды), Владимир Грачев, Виталий Артемьев, Валентин Бубукин, Евгений Лядин, Александр Климачев, Виктор Соколов, Юрий Ковалев, Андрей Крушенок, Виктор Разумовский, Юрий Коротков.}

Геннадий Забелин. Защитник. Выступал за «Локомотив» в течение тринадцати сезонов, был капитаном команды. Обладатель Кубка СССР (1957). Был начальником отдела Управления футбола Спорткомитета СССР, директором школы «Локомотива».

Игорь Зайцев. Нападающий. Играя в «Локомотиве», стал серебряным призером чемпионата (1959) и обладателем Кубка СССР (1957). Затем выступал за киевское «Динамо» (был серебряным призером в 1960-м) и донецкий «Шахтер». 

Виктор Ворошилов. Нападающий. Заслуженный мастер спорта. Перешел в «Локомотив» из куйбышевских «Крыльев Советов». Серебряный призер чемпионата (1959) и обладатель Кубка (1957) в составе «Локомотива», финалист Кубка (1953) в составе «Крыльев». Был капитаном обеих команд. Входит в символический «Клуб Г.Федотова».

Юрий Ковалев. Нападающий и полузащитник. Десять сезонов выступал за «Локомотив», в промежутке провел по одному году в ЦСКА и киевском «Динамо». Серебряный призер чемпионата (1959) в «Локомотиве» и в киевском «Динамо» (1960). Обладатель Кубка СССР (1957). Входил в сборную СССР на Кубке Европы 1960-го.

Виктор Соколов. Нападающий. Лучший бомбардир «Локомотива» в чемпионатах СССР. Серебряный призер чемпионата (1959) и обладатель Кубка страны (1957). В «Локомотиве» провел десять сезонов, заканчивал карьеру в днепропетровском «Днепре».

Евгений Рогов. Защитник. Заслуженный тренер РСФСР. Пришел в «Локомотив» из ВВС и провел в нем восемь с половиной сезонов. Серебряный призер чемпионата (1959) и обладатель Кубка страны (1957). Был капитаном «Локомотива», затем начальником команды и главным тренером. Был также начальником команды в олимпийской сборной и в сборной СССР, главным тренером сборной РСФСР и членом технического комитета УЕФА.   

Подготовил Валерий ВИНОКУРОВ