На следующий год после чемпионства «Локомотив» впервые с 1997 года остался без медалей и впервые с 1993 года:
— без трофеев. Была, правда, победа в только что учрежденном Суперкубке России над принципиальным соперником
— ЦСКА (по пенальти), но рассуждать всерьез о значимости и престиже этого турнира, пожалуй, не стоит.
В чемпионате железнодорожники остались лишь четвертыми. «Бронза» и место в Кубке УЕФА ускользнули на 93-й минуте поединка 30-го тура «Рубин»
— ЦСКА. Помните «бронзовую коленку Дениса Евсикова», автогол которого при¬нес первый комплект наград чемпионата страны казанскому клубу? Но медали своим соперникам «Локомотив» отдал сам. 0:2 и 1:3 — от ЦСКА, 1:2 и 0:0
— с вице-чемпионом «Зенитом», 1:3 и 1:1 — с «Рубином». Прибавьте к итоговым 52 очкам «Локо» 6 потерянных с ЦСКА и отнимите такое же количество от 59 у армейцев. Кто был бы тогда чемпионом («Зенит» набрал 56 баллов, «Рубин» — 53)?
Чемпионат страны «Локомотив» начал катастрофически плохо. 12 очков после одиннадцати матчей — с таким графиком можно рассчитывать только на место в нижней половине таблицы. Сказалась форсированная подготовка к февральско-мартовским матчам Лиги чемпионов. Во второй половине сезона результаты пришли в норму (Лоськов даже выиграл во второй раз соревнование бомбардиров и также во второй раз был признан лучшим футболистом страны), но наверстывать упущенное было очень непросто.
Оставалась только Лига чемпионов, и здесь клубу Филатова и команде Семина удалось реабилитироваться за неудачи на внутренней арене. Переиграв в квалификационном раунде украинский «Шахтер» (очень непросто далась та победа), «Локомотив» вместе с английским «Арсеналом», итальянским «Интером» и киевским «Динамо» попал в группу В. Турнирная борьба в ней складывалась очень напряженно: силы соперников оказались примерно равными и первую команду от последней в итоге отделили всего 3 очка. Железнодорожники сумели занять второе место в группе, опередив «Интер» и «Динамо». Победа же красно-зеленых над «Интером» может считаться одной из самых впечатляющих в истории выступления российских клубов в Лиге чемпионов (хотя поклонники «Спартака» и ЦСКА, наверное, с этим утверждением не согласятся).
21 октября на домашней арене «Локомотив» унизил итальянский суперклуб. 3:0 (голы Лоськова, Ашветии и Хохлова)! Кроме того, были еще боевые ничьи и с тем же «Интером», и с грозным «Арсеналом», домашняя виктория — 3:2 над киевлянами (победный гол коста-риканский джокер Уинстон Парке забил на предпоследней минуте). В общем, место в 1/8 финала «Локомотив» получил по праву.
Весенние игры с будущим финалистом Лиги французским «Монако» могли бы завершиться и более удачно для москвичей. В Москве монегаскам, по признанию их тренера Дидье Дешама, крупно повезло. Всего лишь минимальное поражение — 1:2. А в ответной игре задачу французам облегчил португальский арбитр Кортеш Батишта, удаливший Лоськова уже на 22-й минуте. В итоге 0:1 и память о том, что место среди восьми сильнейших клубов Европы было как никогда реально.
Подводя некоторые итоги выступления «Локомотива» в самом престижном клубном турнире Европы, отметим, что железнодорожники три раза участвовали в Лиге чемпионов и дважды преодолевали групповой этап. «Спартак», для сравнения, также проходил групповую стадию два раза, но участвовал в восьми турнирах. Неудивительно, что о «Локомотиве» футбольная Европа сохранила более приятные воспоминания, чем о других российских клубах. Имеется в виду Лига чемпионов.
2004 год принес красно-зеленым второй чемпионский титул. Титул во многом неожиданный, но не случайный, ибо случайно выиграть чемпионат страны невозможно. «Локомотив» всего лишь три тура из тридцати находился во главе таблицы, но один из них как раз и оказался заключительным, тридцатым. В чемпионате попеременно лидировали «Спартак», «Торпедо», «Зенит», «Крылья Советов»... За три тура до финиша, после победы 3:0 в Санкт-Петербурге вперед вышли армейцы. ЦСКА опережал «Локомотив» на три очка, и казалось, вопрос с чемпионством решен. Но команда Газзаева не смогла обыграть на своем поле «Крылья Советов» и «Динамо», и «плюс три» превратились в «минус один». «Локомотив» финишировал отменно: в семи заключительных матчах чемпионата шесть побед и одна ничья. Выигрыш в Ярославле принес команде Юрия Семина второе «золото». 12 ноября. «Шин¬ник» — «Локомотив» — 0:2 (Билялетди- нов, Сычев).

После первого чемпионского титула прошло всего два года, а состав команды заметно изменился. И не только состав. В чемпионате-2004 «Локомотив» в сравнении с остальными московскими клубами собрал наибольшую зрительскую аудиторию на домашних матчах. Случилось подобное впервые в истории отечественного футбола. Кто бы мог предположить такое еще лет десять-пятнадцать назад?
Конечно, многие болельщики (и особенно болельщицы) шли на Дмитрия Сычева. В то время это был самый популярный футболист страны, скандальный уход из «Спартака» только добавил ему известности. Решение вернуть Сычева в российский чемпионат (2003 год Дмитрий провел во французском «Марселе»), по признанию президента «Локо» Валерия Филатова, стало отличным PR-ходом: «Благодаря Сычеву количество наших болельщиков удвоилось». И 21-летний форвард не разочаровал: лучший бомбардир клуба и сборной, чемпион страны. Это и предопределило его победу в журналистском референдуме «Футбола». Сычев был признан лучшим футболистом года, опередив питерцев Кержакова и Аршавина.
Но по части популярности у Сычева уже появился серьезный конкурент — Динияр Билялетдинов. 19-летний полузащитник проводил первый сезон в Премьер-лиги и стал открытием года. Место в основном составе клуба и молодежной сборной, пять забитых мячей — подобный дебют в свое время был разве что у Марата Измайлова. А летом будущего года Юрий Семин пригласит Билялетдинова в национальную сборную России.
Неоценим вклад во второе чемпионство «Локомотива» ветеранов команды: Овчинникова, Лоськова, Маминова, Пашинина, Евсеева, Сенникова, Нижегородова. Пришлись ко двору и новички: Сергей Гуренко (новичок, конечно же, относительный), Дмитрий Хохлов, грузинские легионеры Малхаз Асатиани и Михаил Ашветия, классный бразильский «опорник» Франсиско Лима. Но были и потери. Особенно сожалела локомотивская торсида об уходе Джейкоба Лексето (по семейным обстоятельствам вернулся на родину). Переход в ЦСКА одного из лучших защитников страны Сергея Игнашевича в стане «Локо» многие восприняли как предательство и предпочли быстро забыть об этом футболисте.
Летом 2004-го на чемпионате Европы в составе сборной России выступали шесть игроков «Локомотива»: вратарь Овчинников, защитники Сенников и Евсеев, хавбеки Лоськов и Измайлов, форвард Сычев.