Футбольный клуб московского "Локомотива" ведет свою историю с 1923 года, когда был образован Клуб им. Октябрьской революции, объединивший сильнейших футболистов Казанской и других железных дорог Московского узла. В конце 1920-х и начале 1930-х годов КОР постоянно фигурирует среди сильнейших футбольных коллективов Москвы, многие его представители (в частности, центровая тройка нападения первой команды КОРА Чеснов - Загрядский - Дементьев, левый край Холин) входят в состав сборных команд Москвы. В 1935 году, когда было создано Добровольное спортивное общество железнодорожников «Локомотив», в его футбольную команду, представлявшую столицу СССР, вошли лучшие игроки КОРа, а также ряд других профсоюзных футболистов: Гранаткин, Ильин, Соколов, Теренков, Жуков, Гвоздков.
Московский «Локомотив» матчем с динамовцами Ленинграда 22 мая 1936 открыл первый розыгрыш клубного чемпионата СССР по футболу. В этом турнире заняли 5 место. В осеннем чемпионате того же года «Локомотив» поднялся на ступеньку выше. Но наибольшего своего успеха "Локомотив" добился в перерыве между двумя чемпионатами страны 1936, стал первым обладателем Кубка СССР. В 1937-1940 гг московский «Локомотив» в чемпионатах страны неизменно демонстрировал хорошую игру, монолитность и стабильность всех своих линий. Это подтверждалось результатами в чемпионатах страны: в 1937 - 6-е место, в 1938 - 8-е, в 1939 году - 5-е, в 1940 - 6-е. В турнирах 1936-1940 гг лишь московский «Спартак» и тбилисское «Динамо» постоянно занимали места выше "Локомотива".
Не так удачно выступал «Локомотив» в розыгрыше Кубка СССР: в 1937 выбыл в 1 / 2 финала от московского «Динамо» (1:4), в 1938 м в 1 / 16 финала уступил киевскому «Динамо» (0:2), в 1939 в 1 / 8 финала - московскому «Спартаку» (0:1). В команду пришли молодые талантливые игроки: защитник Иван Станкович (в "Локомотиве" в 1937-1939 гг), полузащитники Владимир Мошкаркин (1938-1940) и Александр Прохоров (1940), нападающий Василий Карцев (1939-1940). Позже все они перешли в другие московские клубы: «Динамо», ЦДКА и «Торпедо». Форвард Владимир Огурцов провел в клубе четыре сезона (1937-1940), а Виктор Лахонин играл в «Локомотиве» с 1938 по 1950 (первоначально в роли нападающего, а после войны - полузащитником). Тренировал команду, начиная с 1937, Михаил Сушков. В 1941 футболисты «Локомотива» вошли в состав вновь сформированных первых и вторых сборных профсоюзов, однако затем Отечественная война прервала проведение всяческих футбольных соревнований.
В 1945-1950 гг в розыгрышах Кубка СССР «Локомотив» выступал неудачно. Тренировали команду Дмитрий Максимов (1948) и Гавриил Качалин (1949, 1950). В 1952 «Локомотив» второй раз в своей истории вернулся в высшую лигу. В этот год он в турнирной таблице занял 9-е место. В следующем сезоне тренерское место занял бывший тренер ЦДКА - ЦДСА Борис Аркадьев.
Под его руководством клуб занимал следующие места в чемпионатах страны: 1953 - 6-е, 1954 - 10-е, 1955 - 5-е, 1956 - 10-е, 1957 - 4-е, 1958 - 5-е, 1959 - 2 -е, 1960 и 1961 гг - 5-е; выигрыш Кубка СССР в 1957, выступление в финале кубковых соревнований в 1953, 1955, 1958. Многие игроки «Локомотива» входили в список 33 лучших футболистов страны - это были Герман Апухтин, Виталий Артемьев, Юрий Ковалев, Владимир Маслаченко, Евгений Рогов, Виктор Ворошилов, Валентин Бубукин, Вячеслав Спиридонов. В 1962 «Локомотив» занял 13 место в чемпионате страны, в следующем сезоне - 17-е и третий раз в своей истории выбыл из высшей лиги. На тренерском мостике Бориса Аркадьева сменил в 1967 Валентин Бубукин.
В 1972 «Локомотив» вернулся в высшую лигу (на один сезон), а затем с 1975 играл в ней еще шесть лет. В 1972-1978 гг командой руководил Игорь Волчок, в 1979-1980 гг - Виктор Марьенко. Показатели команды в эти годы: 1972 - 15-е место, 1975 - 11-е, 1976 (в) - 15-е, 1976 (о) - 8-е, 1977 - 7-е, 1978 - 15-е, 1979 - 12-е, 1980 - 18-е. Лучшими в эти годы были вратари Золтан Миле, Валерий Самохин и Валерий Новиков, защитники Владимир Перегонцев, Сергей Камзулин, Владимир Рятсовский, Алексей Овчинников, Николай Калайчев и Евгений Александров, полузащитники Юрий Семин, Анатолий Соловьев и Александр Аверьянов, нападающие Гиви Нодия, Валерий Газзаев, Владимир Эштреков и Валерий Петраков, а в самом конце 1970-х годов - защитник Борис Кузнецов, нападающие Юрий Пантелеев, Николай Бадусов и Владимир Муханов. В двух последних сезонах «Локомотива» в высшей лиге отличился как снайпер Петраков.
Лучшим бомбардиром «Локомотива» за сезон остался Виктор Ворошилов (1961 - 19 голов), больше всего мячей в чемпионатах СССР у Виктора Соколова (80), больше всего матчей за "Локомотив" сыграл Валентин Бубукин (232). Семь сезонов московский «Локомотив» играл во второй лиге.
С приходом на место главного тренера Юрия Семина в 1986 результаты «Локомотива» стали улучшаться - после 7 лет подряд, проведенных в 1-й лиге, в 1988 году клуб вернулся в элиту советских чемпионатов, а в 1990 дошел до финала Кубка СССР, где уступил киевскому «Динамо». С 1992 по 2006 гг. президентом клуба был Валерий Филатов, а тренировал клуб вплоть до вызова в сборную в 2005 тренерский тандем Юрий Семин (главный тренер) - Владимир Эштреков. Первое чемпионство пришло к команде в 2002 году. В том же году открылся ультрасовременный стадион «Локомотив». В 1998 и 1999 годах команда дважды подряд доходила до 1 / 2 финала Кубка Обладателей Кубков. В 2001-2003 гг. «Локомотив» участвовал в основном раунде Лиги Чемпионов и дважды выходил в дальнейшие стадии соревнований.
В 2005 г. после почти 19 лет тренерской работы (с перерывом в 1991 г.) с поста главного тренера команды ушел Юрий Семин. Его место занял Владимир Эштреков, который добился с командой третьего места в чемпионате России и выхода в плей-офф Кубка УЕФА. С декабря 2005 по 5 октября 2006 команда тренировал сербский специалист Славолюбом Муслин. Конец сезона 2006 клуб провел под руководством Олега Долматова. 26 декабря 2006 на заседании Совета Директоров клуба было принято решение назначить в качестве президента клуба Юрия Семина, а тренером назначить Анатолия Бышовца.
После окончания чемпионата России 2007 несмотря на победу в Кубке России, за невыполнение поставленной задачи Юрий Семин и Анатолий Бышовец были освобождены от занимаемых должностей. Исполняющим обязанности главного тренера был назначен Ринат Билялетдинов. 6 декабря того же года трехлетний контракт с «Локомотивом» подписал бывший тренер пермского «Амкара» Рашид Рахимов. В 2008 году «Локомотив» занял 8-е место в итоговой турнирной таблице, руководство клуба приняло решение оставить на посту тренера Рахимова.
В начале следующего сезона «Локомотив» неудачно стартовал в чемпионате, а также не сумел выполнить задачу попадания в еврокубки через Кубок России, после чего 28 апреля 2009 Рашид Рахимов был отстранен от работы с командой. До июня 2009 года исполняющим обязанности главного тренера стал Владимир Маминов. 26 мая единогласным решением Совета директоров клуба главным тренером был назначен Юрий Семин. Впрочем, на этом чехарда в клубе железнодорожников не закончилась – в середине сезона 2010 г. у клуба сменился президент, Николая Наумова на этом посту сменила Ольга Смородская, которая в скором времени уволила Семина. Затем недолгое время командой порулил Юрий Красножан, которого позже сменил португалец Жозе Коусейру.