Официальная дата основания клуба под современным названием «Локомотив» — 12 января 1936 года. Однако на официальном сайте клуба указано, что предшественниками Локомотива были железнодорожные клубы «Казанка» (Моск-Казанская ж.д.), появившаяся в 1923 году; Клуб Октябрьской Революции (КОР), выступавший в 1924—1930 гг.; и вновь «Казанка» (Моск-Казанская ж.д.), игравшая в 1931—1935 гг. В соответствии с этим, датой основания клуба может также считаться 12 августа 1923 года.
22 мая 1936 года стал днём рождения чемпионатов Советского Союза по футболу, открывал чемпионат матч между ленинградским «Динамо» и московским «Локомотивом». Первый гол был на счету игрока железнодорожников Виктора Лаврова, но после ленинградская команда забила три гола и выиграла матч со счётом 3:1. Тот сезон железнодорожники закончили на пятом месте, тогда же был и первый завоёванный трофей, им стал первый Кубок СССР в 1936 году, в финале на стадионе «Динамо» в присутствии 20 000 зрителей «Локомотив» обыграл тбилисское «Динамо.
Во второй половине 1950-х годов у «Локомотива» был самый сильный состав за весь советский период его истории. Этому во многом способствовал министр путей сообщения Борис Бещев, который был назначен на этот пост в 1948 году. В 1953 году он привёл в команду Бориса Аркадьева, знаменитого в то время советского тренера, шестикратного чемпиона СССР с «Динамо» и ЦДСА и трехкратного обладателя кубка страны с ЦДСА. Под его руководством в те времена в «Локомотиве» играли будущие чемпионы Европы 1960 года: Владимир Маслаченко и Валентин Бубукин. Он начал постепенно строить команду, которая вскоре стала во второй раз обладателем Кубка СССР в 1957 году. В финале железнодорожники благодаря голу Бубукина, капитана команды, обыграли «Спартак». Матч проходил в Лужниках и собрал 103 000 зрителей, что на тот момент было рекордом страны.
В том же году железнодорожники заняли четвёртое место в чемпионате Советского Союза, набрав столько же очков и имея такую же разницу забитых и пропущенных мячей, как «Спартак», который выиграл бронзовые медали. В 1958 году «Локомотив» стал пятым в чемпионате. Долгожданная медаль была завоевана в 1959 году, это была серебряная медаль первенства Советского Союза. В сезоне 1960 года в первом раунде «Локомотив» стал вторым, но провалил вторую часть чемпионата и закончил турнир только на пятом месте. Аналогичная ситуация сложилась и в следующем сезоне. Вскоре не самые лучшие результаты команды переросли в полномасштабный кризис, результатом которого стал вылет из высшей лиги в 1963 году. Причинами этого стали смена поколений и переход ключевых игроков в более сильные команды.
В 1970—1980-е годы команда балансирует на грани высшей лиги и первой. В то время за команду выступало много талантливых футболистов, ставших впоследствии известными тренерами, таких как Юрий Сёмин, Валерий Газзаев, Гиви Нодия, Валерий Петраков, Виталий Шевченко и другие.

Юрий Семин

Юрий Семин

Новая эра началась с приходом на пост главного тренера Юрия Сёмина в 1986 году. Результаты «Локомотива» стали заметно улучшаться — после семи лет подряд, проведённых в Первой лиге, в 1988 году клуб вернулся в высшую лигу СССР, а в 1990 году дошёл до финала Кубка СССР, где уступил намного более сильному в те времена сопернику — киевскому «Динамо».
С развалом союзных первенств и переходом на рыночные отношения в хозяйстве, началась новая эпоха «Локомотива», ставшая для него самой успешной в истории, продолжавшаяся до ухода из клуба Юрия Семина в 2005 году. Клуб прочно укрепился в элите отечественного футбола, показывал отличные результаты в чемпионате и на международной арене. Немаловажную роль в этом сыграла стабильность в руководстве — с 1992 по 2006 годы президентом клуба был Валерий Николаевич Филатов, а тренировал клуб вплоть до вызова в сборную в 2005 году тренерский тандем Юрий Сёмин (главный тренер) — Владимир Эштреков.
В первом же розыгрыше чемпионата России «Локомотив» занял четвёртое место, что позволило ему на следующий год выступать в еврокубках. Первый официальный еврокубковый матч состоялся 15 сентября 1993 года, железнодорожникам противостоял туринский «Ювентус», где тогда блистал знаменитый итальянец Роберто Баджо, в первом матче он оформил дубль, ещё гол забил другой известный игрок Раванелли. В ответном матче «Ювентус» также оказался сильнее — 1:0.
Вскоре «Локомотив» завоевал первую в своей российской истории медаль — бронзу чемпионата России 1994 года. Форвард железнодорожников Олег Гарин забил за сезон двадцать голов, что стало вторым результатом чемпионата. В список 33 лучших футболистов России по итогам сезона тогда вошли Сергей Овчинников, Алексей Арифуллин, Игорь Чугайнов, Евгений Харлачёв, Алексей Косолапов, Олег Гарин.
На следующий год «Локомотив» поднялся ещё на одно место вверх — клуб сумел завоевать серебро.
Сезоны 1996 и 1997 оказались не столь удачными для московской команды в чемпионате в плане результата: шестое и пятое места. Стоит отметить, что в те годы в команде появился Дмитрий Лоськов, который вскоре станет капитаном команды, культовым игроком для болельщиков.
В чемпионате страны 1998 года «Локомотив» снова смог завоевать медаль чемпионата — бронзу, причем до серебра команде не хватило всего одного очка. В период с 1999 по 2001 годы команда завоевала три серебряные медали, всегда уступая золото «Спартаку».
В 1998 и 1999 годах команда дважды подряд доходила до полуфинала Кубка обладателей Кубков. Причём в последнем случае «Локомотив» уступил римскому «Лацио» только за счёт пропущенного мяча в домашнем матче.
Первое долгожданное чемпионство пришло к команде в 2002 году. Команда отлично начала сезон и уже к седьмому туру единолично возглавила таблицу. К перерыву, связанному с чемпионатом мира команда подходила с первым местом в таблице и только одним поражением. После перерыва «Локомотив» соперничал за первое место с ЦСКА, в итоге чемпионат команды закончили с одинаковыми показателями, был назначен «золотой матч». В нём «Локомотив» переиграл ЦСКА, единственный гол забил Дмитрий Лоськов.

Стадион "Локомотив"

Стадион "Локомотив"

В том же году открылся ультрасовременный стадион «Локомотив».
В 2004 году железнодорожники повторили свой успех двухлетней давности.
В 2005 году после почти девятнадцати лет (с перерывом в 1991) тренерской работы с поста главного тренера команды ушёл Юрий Сёмин. Его место занял Владимир Эштреков, который добился с командой третьего места в чемпионате России и выхода в плей-офф Кубка УЕФА.
С декабря 2005 года по 5 октября 2006 года команду тренировал сербский специалист Славолюб Муслин.
Начало сезона выдалось ужасающим: после четырёх туров у команды было всего одно очко. Переломным моментом стал матч с ЦСКА, который железнодорожники сумели выиграть на последних минутах благодаря голу Ивановича. После этого команда не проигрывала семнадцать матчей подряд и имела неплохие шансы на чемпионство. Но все переменилось после сенсационного вылета из Кубка УЕФА, когда «Локомотив» не смог обыграть полупрофессиональный бельгийский клуб «Зюлте-Варенгем». В команде начался кризис, Славолюб Муслин был уволен, конец сезона 2006 года клуб провёл под руководством Олега Долматова. «Локомотив» не сумел выполнить поставленную перед ним задачу на тот сезон — занять первое или второе место, финишировав только третьим.
26 декабря 2006 года на заседании Совета директоров клуба было принято решение назначить президентом клуба Юрия Сёмина, а тренером — Анатолия Бышовца. По окончании Чемпионата России 2007 года, несмотря на победу в Кубке России, за невыполнение поставленной задачи Юрий Сёмин и Анатолий Бышовец были освобождены от занимаемых должностей. Исполняющим обязанности главного тренера был назначен Ринат Билялетдинов. 6 декабря 2007 года трёхлетний контракт с «Локомотивом» подписал бывший тренер пермского «Амкара» Рашид Рахимов.
В 2008 году в чемпионате железнодорожники повторили результат предыдущего сезона, однако, Рахимов остался на своём посту, имея большой кредит доверия от президента клуба Николая Наумова. В начале следующего сезона «Локомотив» неудачно стартовал в чемпионате, а также не сумел выполнить задачу попадания в еврокубки через Кубок России, после чего 28 апреля 2009 года Рашид Рахимов был отстранён от работы с командой. До июня 2009 года исполняющим обязанности главного тренера стал бывший игрок «Локомотива» Владимир Маминов.
26 мая единогласным решением Совета директоров клуба главным тренером был назначен Юрий Сёмин, который одновременно вошёл в состав совета директоров и имеет наравне с президентом клуба приоритетное право голоса при решении трансферных вопросов. В первой же игре под руководством Юрия Сёмина команда уступила Сатурну 0:2. Затем «Локомотив» провёл серию из десяти матчей без поражений. По результатам сезона Локомотив занял четвёртое место, дающее право играть в Лиге Европы УЕФА, уступив бронзу «Зениту» только по разнице мячей. Также «Локомотив» стал единственной командой, не проигравшей дома ни одного матча.
В первом матче сезона 2010  премьер-лиги «Локомотив» уступил «Рубину» со счётом 2:0. Первая победа была одержана в следующем туре, 20 марта, в матче с «Крыльями Советов» со счётом 3:0 (сначала забил Сычев, потом дубль оформил Алиев). Далее победы чередовались с поражениями, намечался кризис, пик которого пришёлся на август: команда выбыла из борьбы за кубок России и Лигу Европы, потерпела ряд разгромных поражений в чемпионате. В прессе стали ходить активные слухи о снятии с поста главного тренера команды Юрия Сёмина, однако совет директоров принял решение оставить Сёмина на своём посту. После этого у команды началась одиннадцатиматчевая беспроигрышная серия, итогом которой стало пятое место в чемпионате.
Посередине сезона у клуба сменился президент, Николая Наумова сменила Ольга Смородская, у которой вскоре начался конфликт с главным тренером команды, итогом которого стала отставка Юрия Семина по окончании сезона.
1 июля 2011 года на пост наставника «Локомотива» был назначен Жозе Коусейру.