С промяната на политическата система у нас след 10 ноември 1989 г. за ЦСКА започват трудни години с много тежки изпитания. Вече я няма мощната подкрепа на Министерството на отбраната; занемарена и разграбена е по-голямата част от материалната база, която ползва армейският клуб – хотел „Олимп“ в курорта Боровец, морската база в Китен, хижа „Сълзица“ на Витоша, базата в Панчарево и клубния стадион в Борисовата градина. В тази трудна обстановка президент става Валентин Михов, който полага неимоверни усилия, за да съществува клуба.

За сезон 1990/91 година са привлечени много нови футболисти вместо напусналите (освен атомното трио Костадинов–Пенев–Стоичков) Илия Вълов, Стефан Бачев, Ивайло Киров, Петър Витанов и др. Привлечени са таланти като Христо Марашлиев, Радослав Видов, Антон Димитров, Стойчо Стоилов, Анатоли Нанков.

Всичко това довежда до срив на старта – до четвъртия кръг отборът има само едно равенство и три загуби, изпратили шампиона от миналото първенство на последното 16-о място. Това довежда до треньорска рокада. Димитър Пенев е сменен от Аспарух Никодимов (за втори път), а помощници стават Цветан Йончев и Стоян Йорданов. Отборът е стабилизиран и в крайна сметка финишира втори, отстъпвайки неочаквано на провинциалния Етър, воден от Георги Василев-Гочето.

Паро обаче вече е поставил основите на нов отбор за следващия шампионат (1991/92). Отбора напускат Мимитър Младенов, Марин Бакалов, Георги Георгиев, Румен Апостолов, Мариус Уруков и Тодор Стоянов. Отново червения екип обличат Георги Велинов, Лъчезар Танев, Красимир Безински и Ивайло Киров. Привлечени са доказани фигури като Павел Дочев, Стефан Колев, Велиян Парушев, Росен Кирилов, Йордан Лечков, Кирил Метков, Йордан Маринов, Ивайло Андонов, Тодор Праматаров и Стефан Драганов.

Битката с вечния съперник Левски е страховита. „Сините“ чакат титла вече три години, а имат нов и амбициозен президент – Томас Лафчис. ЦСКА започва първенството с шест поредни победи и допуска първата загуба чак в 13-ия кръг като гост на Етър. Въпреки че губи в следващия кръг вечното дерби с 1:2, завършва есенния полусезон като лидер с точка повече от Левски. През пролетния полусезон отборът се представя още по-добре. Прави стратегическо реми (2:2) срещу опонента Левски и допуска само една загуба (изненадващо като гост на средняка Миньор Перник). За втори път в клубната история е постигната победа с двуцифрен резултат в „А“ група - на 2 май 1992 г. на „Армията“ е разгромен Берое с 10:2 (героят на мача е Кирил Метков, реализирал четири попадения).

Титлата е спечелена с две точки повече от Левски. Инерцията обаче бързо е изгубена – в следващите три сезона ЦСКА тотално отстъпва на Левски, който печели три поредни титли, при това убедително, но не и без солидна подкрепа от най-високо политическо ниво. Особено слаб е сезон 1994/95, независимо че клубът има нов президент – собственикът на тогавашната могъща групировка „Мултигруп“ Илия Павлов и не липсват финанси. В шампионата армейците завършват пети на рекордните 33 точки след „сините“, а на 23 септември 1994 г. инкасират най-тежката си загуба от вечния съперник (1:7). Основната причина е непрекъснатият треньорски кадрил. Последователно като наставници се изреждат петима специалисти – Божил Колев, Цветан Йончев (за втори път), Спас Джевизов, Христо Андонов – Пелето и Цветан Атанасов. ЦСКА е стигнал дъното.

В този мрачен 4-годишен период обаче има два проблясъка. Първият е спечелената национална купа през 1993 г. (1:0 на финала с Ботев Пловдив), а вторият са двата проблясъка на международната сцена срещу италианските Парма и Ювентус.

В турнира за Купата на УЕФА през сезон 1991/92 на 1/32-финал съперници са „пармалатите“ с треньор Невио Скала. Първият мач, преминал в глуха защита от италианците, завършва при нулево  равенство. На реванша ЦСКА е напълно равностоен и не изпуска шанса си. Джони Велинов спасява дузпа на национала Алесандро Мели, а след това е наказана единствената грешка в италианската защита за целия мач. В 88-та минута сърцатият защитник армейците Велиян Парушев с атрактивен плонж с глава бележи за 1:1 и с гол повече на чужд терен класира тима за следващия кръг. За съжаление там го чака германският колос Хамбургер, който взима победи и в двата мача (2:0 като домакин и 4:1 като гост).

Другият момент за историята отново е за Купата на УЕФА, но през сезон 1994/95. В първи кръг е остранен (3:0 като домакин и 0:0 като гост) арменския Арарат. Във втория обаче съперник е най-титулувания италиански клуб - Ювентус. Тимът е воден от Марчело Липи (който 12 г. по-късно ще направи Италия световен шампион), а съставът е пълен със суперзвезди – Дидие Дешан, Джанлука Виали, Фабрицио Раванели, Чиро Ферара, Алесандро дел Пиеро... На „Армията“ ЦСКА надиграва напълно именития си съперник в непрекъсната гонитба в резултата. Победата с 3:2 идва след две попадения на Петър Михтарски (второто от пряк свободен удар от 25 метра е истински шедьовър) и великолепен гол на дебютанта Милен Радуканов. За съжаление административен пропуск (свързан с картотекирането на Петър Михтарски) довежда до анулиране на резултата. На реванша Старата госпожа играе мобилизирано и постига разгромна победа с 5:1, като и петте попадения са на белокосия нападател Фабрицио Раванели.