В 1995-м спартаковцы сдали свои чемпионские полномочия владикавказской «Алании», откатившись на третью ступень пьедестала, но превосходно выступили в Лиге чемпионов, выиграв все шесть матчей в своей группе: у «Легии» (2:1, 1:0), «Блэкберна» (1:0, 3:0) и «Русенборга» (4:2, 4:1). Москвичи вышли в четвертьфинал, где весной 1996-го уступили французскому «Нанту» (0:2, 2:2). В этих матчах команду возглавлял уже новый главный тренер — Георгий Ярцев. Романцев по окончании сезона- 95 решил взять годовую паузу и сосреное время они лучше пробили серию пенальти — 4:2.
Дважды подряд, в 92-м и 93-м годах, лучшим футболистом сезона по итогам референдума еженедельника «Футбол» признавался капитан «Спартака» Виктор Онопко.
В 93-м в команду вернулся, увы, ненадолго, Федор Черенков. В 23 августа 1994 года в Москве на стадионе «Динамо» состоялся его прощальный матч: «Спартак» сыграл с итальянской «Пармой» (1:1). Впрочем, с качественным пополнением у «Спартака» в эти годы проблем не было. Из «Черноморца» пришли два одессита — Юрий Никифоров и Илья Цымбаларь, из «Локомотива» — Дмитрий Аленичев, из «Памира» — Мухсин Мухамадиев, вернулся из Франции и Сергей Родионов. Дебютировал в команде Андрей Тихонов из подмосковного «Титана» (Реутов).
В групповом турнире Лиги чемпионов «Спартак» вновь не снискал лавров, уступив французскому «Пари-Сен-Жермену» (1:2, 1:4) и разделив очки с киевским «Динамо» (2:3, 1:0) и немец доточиться на работе со сборной России, которой предстояло выступать в финальной части чемпионата Европы в Англии. А Ярцев, несмотря на огромные кадровые потери (уехали в зарубежные клубы Юран, Кульков, Онопко, Шмаров, Черчесов, закончил карьеру игрока Родионов, а после чемпионата Европы разъехались Никифоров, Мухамадиев, Тяпушкин, Андрей Иванов, Афанасьев, Масалитин), нашел выход. Он смело ввел в основу молодых ребят из дубля, среди которых особенно выделялся Егор Титов. И они оказались достойны славы своих предшественников. Финишировав в первенстве вровень с «Аланией», а затем выиграв у нее дополнительный «золотой» матч (2:1), ярцевский «детский сад» в четвертый раз стал чемпионом России. Вышел «Спартак» и в финал Кубка России, но там в драматичной борьбе уступил набирающемуся сил «Локомотиву» (2:3).
Победу в чемпионате спартаковцы посвятили светлой памяти своего основателя и патриарха, легендарного «Чапая» и «Деда» — Николая Петровича Старостина, который скончался в феврале 1996 года.
Осенью в Кубке УЕФА спартаковцы выиграли у «Кроации» из Загреба (1:3, 2:0), датского «Силкеборга» (3:2, 2:1), но уступили немецкому «Гамбургу» (0:3, 2:2).