Свою команду Тарханов начал формировать еще по ходу прошлого сезона, а после его завершения решительно отказался от услуг ветеранов садыринского призыва. Клуб покинули Быстров, Брошин (оба ушли в «Зенит», Санкт-Петербург), Иванов (в «Маккаби», Герцлия, Израиль), Колотовкин, Гришин, Семенов (все — в «Динамо», Москва), Демченко («Аякс», Амстердам, Голландия), Синев (уехал в Испанию, позже вернулся, играл за «КамАЗ», «Арсенал», Тула, «Торпедо-ЗИЛ», «Рубин»). Ушел из команды Колесников.
Знаковой чертой нового ЦСКА стала блистательная средняя линия, в центре которой засверкало трио Радимов — Хохлов — Семак. Их поддерживали активные фланги, где в разных сочетаниях играли Антонович, Карсаков (вернулся из «Торпедо», Москва), Ульянов (оттуда же), Алексей Герасимов (из «Локомотива», Нижний Новгород). В центре защиты играл капитан команды Бушманов. Линия обороны строилась в течение всего сезона. Справа чаще всего выступал Минько, слева — Мамчур, в центре, кроме Бушманова, в разные периоды — Гайсумов (из «Эрзу», Грозный), Машкарин, Градиленко (бывший спартаковец, играл в тольяттинской «Ладе»), Глушаков (несколько сезонов играл в чемпионате Финляндии). Ворота защищали: в первой половине сезона Новосадов, а с конца июня — Плотников. В атаке сначала играли двое — Файзулин и Лебедь (воспитанник украинского футбола, пришел из «Спартака», Владикавказ), позже — как правило, кто-либо один из них. Тем не менее, результативность армейцев по сравнению с минувшим сезоном выросла почти вдвое. Лучшим бомбардиром с десятью голами стал Карсаков. У Лебедя — 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-го тура, армейцы одержали семь (!)  побед подряд: 
24 августа. Москва. ЦСКА — «КамАЗ» — 4:2 
5 сентября. Москва. «Динамо» М — ЦСКА — 2:3 
15 сентября. Москва. ЦСКА — «Торпедо-Лужники» — 2:0 
19 сентября. Ростов-на-Дону. «Ростсельмаш» — ЦСКА — 0:5 
28 сентября. Москва. ЦСКА — «Зенит» — 1:0 
2 октября. Сочи. «Жемчужина» — ЦСКА — 0:1 
12 октября. Москва. ЦСКА — «Алания» — 2:0 
Команда  поднялась с пятого места на третье, уступая всего три очка «Ротору» и  два — «Спартаку». Оставалось всего три тура до финиша чемпионата,  которые стали кошмаром для армейских болельщиков. 
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. В ответном матче в начале второго тайма Минько открыл счет, но за четверть часа до финального свистка хозяева его сравняли. Армейцы предприняли затяжной штурм, но в следующую стадию им пробиться не удалось.