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

С началото на сезон 1995/96 г. за треньор на ЦСКА е назначен бившия играч на отбора Пламен Марков. Той се опитва да стабилизира тима, но не му се отдава, и след есенния поусезон е освободен. На негово място изненадващо е назначен бившият треньор на Етър (титла през 1990/91 г.) и на вечния съперник Левски (титли през 1993/94 г. и 1994/95 г.) Георги Василев-Гочето. Именно последното е посрещнато на нож от част от клубното ръководство, от ветераните и от феновете на отбора. В отговор великотърновският специалист прави култовото си изказване: „На „Армията“ е трудно за „външни“ хора, защото там, в Борисовата градина, съскат змии“, но без да конкретизира кои са те. Георги Василев обаче затваря устите на критиците, вкарвайки ред в отбора (извежда го от осмо на пето място) с по-голям точков актив от есента на 1995 г. Същевременно е допусната само една загуба – 1:2 като гост от Локомотив (Пд), а Левски е победен с 1:0 след попадение на Петър Михтарски. Това дерби остава в митологията като „змийското дерби“. След мача разгневени „сини“ ултраси, недоволни от ръководството на рефера Веселин Богданов от Велико Търново, хвърлят по него жива змия.

Намирайки опора в лицето на своите помощници Стойчо Младенов и Николай Илиев-Галибата и на новия изпълнителен директор Борис Станков (бивш играч на клуба), Василев успява да изгради един от последните звездни състави на ЦСКА. Тимът е подсилен с пловдивчанина Костадин Видолов-Магьосника и завърналите се от чужбина Ивайло Андонов и Георги Йорданов-Ламята, бивш играч на Левски.

Малко изненадващо опонент за титлата се оказва влезлият само две години по-рано в елита Нефтохимик (Бургас) с двама болезнено амбициозни и безкрайно ексцентрични в поведението си ръководители – президентът Христо Порточанов и треньорът Димитър Димитров-Херо. Именно от този отбор ЦСКА губи по най-скандален начин още в първия кръг на шампионата. Армейците водят след първото полувреме с 1:0, когато на почивката Порточанов нахлува в съдийската стая с пистолет на кръста и крещи на главния рефер Димо Момиров: „Ще ти изпразня пълнителя в корема“. През второто полувреме „шейховете“ абсолютно „закономерно“ правят обрат в резултата (2:1). Това обаче не уплашва клуба с президент Илия Павлов – напротив, мобилизира всички на „Армията“ до краен предел. След осмия кръг армейците поемат водачеството и не го изпускат до края.

След финала на есенния полусезон ЦСКА е лидер с аванс от 7 точки пред Нефтохимик. Решаващият удар „червените“ нанасят в първия пролетен кръг, когато на „Армията“ побеждават с 1:0 с попадение на голмайстора Ивайло Андонов.
През пролетния полусезон е допусната само една загуба – 0:1 от Локомотив (София), в 25-тия кръг. Тя прекъсва серията от 23 мача на отбора без поражение. В крайна сметка след 5-годишна пауза армейците печелят отново шампионската титла. Тя е дублирана и със спечелването на националната купа (11-ти дубъл в клубната история). На четвъртфинала армейците преодоляват (2:0 и 1:1) шампиона и носител на националната купа от предния сезон Славия. На финала убедително е надигран вечния съперник Левски с 3:1.

В основата на този успех на ЦСКА са Петко Петков, Адалберт Зафиров, Добромир Митов, Филип Филипов, Галин Иванов, Стефан Лулчев, Анатоли Нанков, Милен Петков, Ивайло Андонов (голмайстор на отбора с 18 попадения), Димитър Иванов, македонецът Ристе Милославов, Петър Жабов, Илия Войнов, Костадин Видолов, Методи Деянов, Георги Йорданов, Иво Славчев, Кънчо Йорданов и младоците Мартин Петров и Стилиян Петров.

В следващите два шампионата ЦСКА отстъпва в борбата за титлата с Левски и ловешкия Литекс, който става шампион. Същевременно за пореден път треньор на ЦСКА става Димитър Пенев. Той успява да спечели през 1999 г. националната купа и в същото време да интегрира в отбора младоците Димитър Бербатов, Мартин Петров и Стилиян Петров.

На международната сцена ЦСКА изиграва няколко запомнящи се мача. Първо са двата двубоя със Стяуа през есента на 1997 г. В дебютния мач армейците играят великолепно като гости, правейки 3:3, след като до 77-ата минута водят с 3:1. На реванша предпазливата тактика и липсата на международен опит водят до изненадваща загуба с 0:2 и отпадане от квалификациите за Шампионската лига.

Много по-успешна е международната изява през сезон 1998/99 г. в турнира за Купата на УЕФА. Последователно са отстранени Белшина (Блрс), Молде (Нор), Сервет (Швейц), преди да дойде ред на сблъсъка с испанския гранд Атлетико (Мадрид). Негов треньор е великият Ариго Саки (европейски клубен шампион с Милан), който разполага със звезди като световния шампион с Бразилия Жуниньо Паулища, европейския клубен шампион с Цървена звезда Владимир Югович, аржентинския национал Хосе Чамот и испанските лидери Кико Нарваес и Хуан Валерон, както и чешкия национал Радек Бейбъл. Армейците се представят достойно след загуба с 0:1 като гост и 2:4 като домакин.

И в следващия сезон 1999/2000 г. в същия турнир ЦСКА се представя запомнящо се. В първия кръг убедително (3:0 като гост и 5:0 като домакин) е победен северноирландския Портадаун. В следващия кръг съперник е силният английски тим Нюкасъл с треньор Боби Робсън и големия голмайстор Алън Шиърър. На „Българска армия“ в първия мач гостите са по-добри и побеждават с 2:0. Своите истински възможности ЦСКА показва на „Сейнт Джеймсис Парк“, играейки като равен с равен и завършвайки 2:2. Този мач е лебедовата песен на треньор №1 на България за 20-ти век на международната клубна сцена Димитър Пенев-Стратега.