Свою команду Тарханов начал формировать еще по ходу прошлого сезона, а после его завершения решительно отказался от услуг ветеранов садыринского призыва. Клуб покинули Быстров, Брошин (оба ушли в «Зенит», Санкт-Петербург), Иванов (в «Маккаби», Герцлия, Израиль), Колотовкин, Гришин, Семенов (все — в «Динамо», Москва), Демченко («Аякс», Амстердам, Голландия), Синев (уехал в Испанию, позже вернулся, играл за «КамАЗ», «Арсенал», Тула, «Торпедо-ЗИЛ», «Рубин»). Ушел из команды Колесников.
Знаковой чертой нового ЦСКА стала блистательная средняя линия, в центре которой засверкало трио Радимов — Хохлов — Семак. Их поддерживали активные фланги, где в разных сочетаниях играли Антонович, Карсаков (вернулся из «Торпедо», Москва), Ульянов (оттуда же), Алексей Герасимов (из «Локомотива», Нижний Новгород). В центре защиты играл капитан команды Бушманов. Линия обороны строилась в течение всего сезона. Справа чаще всего выступал Минько, слева — Мамчур, в центре, кроме Бушманова, в разные периоды — Гайсумов (из «Эрзу», Грозный), Машкарин, Градиленко (бывший спартаковец, играл в тольяттинской «Ладе»), Глушаков (несколько сезонов играл в чемпионате Финляндии). Ворота защищали: в первой половине сезона Новосадов, а с конца июня — Плотников. В атаке сначала играли двое — Файзулин и Лебедь (воспитанник украинского футбола, пришел из «Спартака», Владикавказ), позже — как правило, кто-либо один из них. Тем не менее, результативность армейцев по сравнению с минувшим сезоном выросла почти вдвое. Лучшим бомбардиром с десятью голами стал Карсаков. У Лебедя — 8, у Файзулина и Герасимова — по 6. По 5 мячей забили Хохлов и Радимов, по 4 — Ульянов и Семак. Даже защитники Гайсумов, Мамчур и Машкарин отличились по два раза.
Армейцы финишировали в четвертом чемпионате России на шестом месте, хотя по игре, показанной в некоторых матчах, могли претендовать и на большее. И все же можно признать, что сезон команде удался, и она на правильном пути. Команда в 30 матчах одержала 16 побед, потерпела 9 поражений и пять раз сыграла вничью. Мячи — 56-34.
Дублеры армейцев столицы (тренер — Ю.Н. Аджем) вместе с резервистами других команд участвовали в турнире третьей зоны третьей лиги первенства России и заняли среди 23 участников девятое место. Лучший бомбардир — А. Антипов (11 голов).
В матчах на Кубок России 1995/96 гг. армейцы, победив «Балтику» — 2:1 (Бушманов, Градиленко) и нижегородский «Локомотив» — 3:0 (Семак — 2, Карсаков), вышли в 1/4 финала.
В национальной сборной Радимов и Лебедь сыграли по одному матчу. Правда, это были отборочные игры чемпионата Европы.
А вот в составе молодежной сборной на поле постоянно выходило не менее трех армейцев столицы. Всего в официальных матчах сыграли 7 представителей ЦСКА: Машкарин (4 игры), Хохлов (3), Радимов (3, 2 гола), Семак (3, 1), Лебедь (3, 5), Файзулин (2), Герасимов (1).
В юниорской сборной по 4 матча сыграли Лысенко, Радимов, Хохлов и Семак, 3 — Орещук.
За юношескую сборную 1976 г.р. играли Владимиров, Агеев, Цаплин, Ляпкин, Дасаев, Лысенко.
За сборную 16-летних — воспитанники СДЮШОР ЦСКА Кузнецов и Чернов. А за команду годом моложе — Штромбергер, Миронов, Исаков, Прядко, Булыкин, Борушевский, Еманов.
В список «33 лучших» по итогам сезона-95 вошли центральный защитник Е. Бушманов (№ 2) и полузащитник В. Радимов (№ 1).
В следующем сезоне команда ЦСКА поднялась еще на одну строчку в итоговой таблице.
Селекционная работа, начатая Тархановым в предыдущем сезоне, активно продолжалась. Выбыли Плотников — в «Альбасете» (Испания), Градиленко, Антонович — оба в «Ротор», Гайсумов — в «Сокол» (Саратов), Гущин — в московское «Динамо», Файзулин — в «Расинг» (Испания), Глушаков (играл в Казахстане и Туркмении). Среди новобранцев межсезонья отметим вратаря Д. Тяпушкина, защитника А. Иванова, нападающего А. Мовсесьяна (все — из московского «Спартака»), крайнего полузащитника А. Шутова («Ростсельмаш»), нападающего Ю. Матвеева («Уралмаш») и вернувшегося из Саудовской Аравии О. Сергеева. Последний, правда, уже в мае выбыл в «Аланию».
В новом сезоне вместе с главным тренером работали начальник команды Г. Штромбергер, тренеры В. Федотов и В. Осадчий.
А летом в ЦСКА впервые появились легионеры из дальнего зарубежья — бразильский защитник Леандро Самарони и его земляк — атакующий хавбек Леонидас. С приходом этих футболистов, а также форварда Эдгараса Янкаускаса из литовского «Жальгириса» резко повысилась зрелищность и, что еще важнее, результативность игры команды. И это притом, что летом же уехали в испанские клубы «Сарагоса» и «Расинг» (Сантандер) — Радимов и Ульянов, в корейские «Самсунг» и «Юконг» — Матвеев и Карсаков.
Игра ЦСКА во второй половине сезона вселяла в сердца его приверженцев самые смелые надежды. Начиная с 25-го тура, армейцы одержали семь (!) побед подряд:
Команда поднялась с пятого места на третье, уступая всего три очка «Ротору» и два — «Спартаку». Оставалось всего три тура до финиша чемпионата, которые стали кошмаром для армейских болельщиков.
19 октября в Калининграде местная «Балтика», взяв в железные клещи прессинга наших хавбеков, заставила ЦСКА капитулировать — 1:2.
25 октября проходил предпоследний тур чемпионата. Все московские клубы, кроме «Торпедо-Лужники», выступали в роли хозяев. «Спартак» играл на Восточной улице, «Локомотив» — у себя в Черкизове, «Динамо» — в Петровском парке, а стадион в Лужниках был закрыт на реконструкцию. Лишь армейцам не нашлось места на столичной земле, и они принимали новороссийский «Черноморец» в подмосковном Селятине. В игре команды что-то сломалось. Чувствовалось, что одиннадцать ребят на поле думают о чем угодно, только не об игре. Провалы в обороне, беспомощность в атаке привели к закономерному поражению — 1:3. Две неудачи поставили крест на чаяниях болельщиков. Не помогла и победа над земляками-железнодорожниками в заключительном матче. Зато «большой ЦСКА» получил повод разорвать отношения с футбольным клубом Тарханова.
Но пока — об итогах сезона. Команда ЦСКА заняла в чемпионате России 5-е место, повторив лучший свой результат 1992 года. В 34 играх она одержала 20 побед и потерпела восемь поражений, сыграв 6 раз вничью. Забито 58 мячей, пропущено — 35. Больше всех забили Хохлов и Герасимов — по 10 мячей.
В список «33 лучших» включили защитников Е. Бушманова и В. Минько и полузащитника Д. Хохлова (всех — под № 2). Удостоились армейцы столицы и двух командных призов — «Гроза авторитетов» и «Агрессивный гость».
Д. Тяпушкин отыграл в чемпионате 14 матчей «насухо»!
Дублеры ЦСКА под руководством Ю. Аджема и В. Колядко выступали в третьей зоне третьей лиги и заняли 10-е место среди 20 участников. В атаке команды заметные роли играли форвард И. Семшов (10 голов) и полузащитники братья-близнецы С. и А. Антиповы (соответственно — 9 и 5).
В розыгрыше Кубка России 1995-1996 гг. армейцы уступили в 1/4 финала волгоградскому «Ротору» — 0:2.
В матчах национальной сборной играли четверо представителей ЦСКА. В весенних товарищеских играх и в финальном турнире чемпионата Европы участвовали Е. Бушманов, В. Радимов и Д. Хохлов. В августовском товарищеском матче со сборной Бразилии играл В. Радимов, а в отборочных играх ЧМ-98, кроме того, В. Минько и Е. Бушманов.
Молодежная сборная проводила отборочные игры чемпионата Европы, в которых на поле выходили Д. Хохлов и С. Семак.
В августе армейцы приняли старт в очередном розыгрыше Кубка УЕФА. В квалификационном раунде они дважды обыграли исландскую команду «Акранес» — 2:0 (Карсаков, Янкаускас) в гостях и 4:1 (Мовсесьян — 2, Леонидас, Янкаускас) дома. В 1/32 финала в соперники ЦСКА достался именитый голландский клуб «Фейеноорд» из Роттердама. В Москве красно-синие восемь минут не дотерпели до ничьей — 0:1. В ответном матче в начале второго тайма Минько открыл счет, но за четверть часа до финального свистка хозяева его сравняли. Армейцы предприняли затяжной штурм, но в следующую стадию им пробиться не удалось.