Walerij Tichonienko, który aktualnie jest szkoleniowcem żeńskiej reprezentacji Rosji w koszykówce, został pierwszym trenerem CSKA Moskwa w 2000 roku. Miał to być początek powrotu "Armii Czerwonej" do grona najlepszych ekip na Starym Kontynencie. Zespół ten świetnie radził sobie na rodzimym podwórku, ale poza jego granicami było zdecydowanie. Tichonienko na tym stanowisku zastąpił Stanisława Eremina, który przez sześć sezonów prowadził CSKA. Jedynym sukcesem na arenie europejskiej było zajęcie 3. miejsca w Eurolidze. Miało to miejsce w 1996 roku. Później nie udało się nawet zbliżyć do tego wyniku.
Kiedy Tichonienko objął prowadzenie "Red Army" zdecydowaną większość składu stanowili Rosjanie, z kilkoma dodatkami z Europy oraz rodzynkiem ze Stanów Zjednoczonych. Jak się później okazało zmiany były bardzo potrzebne, ale Walerij nie sprostał wymaganiom. W rozgrywkach Superligi nie było wówczas mocnych na ekipę Uralu Great Perm, która dwukrotnie sięgnęła po mistrzostwo Rosji. Natomiast CSKA nie zdołało nawet wywalczyć miejsca na podium! Był to wielki cios, wręcz nokaut dla klubu z tak wspaniałymi tradycjami. Warto jednak podkreślić, że "Red Army" w 2001 roku dotarło do Final Four Euroligi, ale niewiele zwojowało. Nie udało się poprawić, albo chociaż powtórzyć tego wyczynu w kolejnym sezonie, bowiem CSKA odpadło już na etapie Top16, gdzie lepsi okazali się koszykarze Maccabi Tel Awiw, oraz TAU Ceramiki Vitorii.
Wywołano wówczas wielką lawinę. Postanowiono zrezygnować z usług Tichonienki. Z podstawowego składu pozostał zaś jedynie Zakhar Paszutin. Drużynę opuścili wielcy indywidualiści. Mirsad Turckan postanowił obrać kierunek Półwysep Apeniński, bowiem parafował on kontrakt z Montepaschi Sieną. Za ocean, do Memphis wyruszył Gordan Giricek.
Włodarze CSKA zniesmaczeni wcześniejszymi fatalnymi wynikami zasięgnęli więc posiłków z najwyższej półki. Nowym szkoleniowcem został niezwykle utytułowany Dusan Ivković. 66-letni Serb stanął przed trudnym wyzwaniem, ale warto podkreślić, iż parafował on 3-letnią umowę. Wymagania sterników "Armii Czerwonej" były spore - mistrzostwo Rosji, a także Final Four Euroligi. Ivković pozyskał wówczas kilku świetnych, utalentowanych koszykarzy, jak Theodoros Papaloukas, John Robert Holden, Darius Songaila. Sprowadzono również doświadczonego Chrisa Gatlinga, który jednak nie znalazł uznania w oczach Serba.
Ivković potrzebował czasu aby zgrać ze sobą wszystkich zawodników. Nic więc dziwnego, że początek rozgrywek dla tego teamu nie był w wymarzonym stylu. Z biegiem czasu zaczynało to wyglądać coraz lepiej, i widać było, że ekipa CSKA staje się coraz silniejsza. Bilans 12 zwycięstw w 14 meczach fazy grupowej Euroligi potwierdzał wielki potencjał tej drużyny. "Red Army" dotarło do Final Four, ale tam ostatecznie zajęło 4. miejsce, natomiast w lidze powrócili na tron.
Kolejny sezon przyniósł wiele zmian. Oczywiście na swoim stanowisku pozostał Dusko, w którego w Moskwie nadal wierzono. Włodarze 16-krotnych Mistrzów Rosji mieli jednak ku temu podstawy. W zespole doszło do kilku roszad, które sprawiły, że team ten - przynajmniej na papierze - prezentował się jeszcze bardziej okazale. CSKA w fazie grupowej Euroligi musiało zmierzyć się z bardzo silnymi drużynami. Mowa tutaj o Maccabi Tel Awiw, Panathinaikosie Ateny, Montepaschi Siena, Skipperze Bolonia, Unicaji Malaga i Żalgirisie. Krka Nove Mesto zdecydowanie odstawało umiejętnościami od pozostałych ekip. Wówczas "Armia Czerwona" pokazała się z najlepszej strony, zajmując w tej grupie (zwanej wówczas grupą śmierci) 1. miejsce. W Final Four, w półfinale podopieczni Ivanovicia musieli jednak uznać wyższość klubu z Tel Awiwu. Natomiast w walce o 3. lokatę pokonali team ze Sieny. CSKA zdołało również obronić mistrzostwo Rosji.
Trzeci rok pracy w moskiewskiej ekipie nie przyniósł zbyt wielkiego progresu. 66-letni Serb podjął jeszcze przed rozpoczęciem rozgrywek kilka bardzo odważnych decyzji. Przede wszystkim zmiana warty na pozycjach podkoszowych. W zespole pojawił się David Andersen, a także Aleksiej Sawraszenko. Pomimo kontrowersyjnych transferów Dusan wiedział co robi. Po raz trzeci z rzędu triumfował w Superlidze, na dokładkę dołożył Puchar Rosji, ale nie udało się dotrzeć chociażby do finału Final Four Euroligi - 4. pozycja.
Sternicy "Red Army" nie przedłużyli umowy z Ivkoviciem. Tym zasięgneli pomocy z Włoch. z Treviso do Moskwy przeniósł się Ettore Messina, który prowadząc włoskie kluby odnosił spore sukcesy. Jego złoty okres nastał jednak w CSKA. David Vanterpool, Matjaz Smodis, Trajan Langdon oraz Thomas van den Spiegel byli nowymi nabytkami rosyjskiego hegemona. Jak się później okazało wszyscy Ci zawodnicy wnosili bardzo wiele do drużyny.
Pierwszy rok pod egidą Messiny, był wręcz niesamowity. Team ten wspiął się bowiem na wyżyny swoich umiejętności. 50-letni szkoleniowiec wykrzesał z niego wszystko co się tylko dało. Na parkietach Superligi nikt nie zdołał nawiązać równorzędnej walki z "Armią Czerwoną". Podobnie było w rozgrywkach Pucharu Rosji. Natomiast w Eurolidze, w finale CSKA w pokonanym polu zostawiło wielkie Maccabi Tel Awiw. Tym samym klub ten był najlepszym na Starym Kontynencie, po raz pierwszy od 35 lat!
W kolejnych latach CSKA nadal znajdowało się w ścisłej czołówce ekip europejskich - w 2008 triumf, w 2007 i 2009 występ w finale. W walce o mistrzostwo Rosji nikt nie miał nawet cienia złudzenia, aby zdetronizować "Red Army". Udało się tego dokonać jedynie w Pucharze Rosji, który po raz ostatni został zdobyty przez ten zespół w 2007 roku.
Jak dobitnie widać team ten zawsze liczył się w walce o najwyższe trofea. Jednak wszystko może ulec przemianie. Dlaczego? Kryzys gospodarczy, dotknął bowiem w największym stopniu właśnie rosyjskie kluby. Niektóre z nich są wręcz na skraju bankructwa. W tak fatalnej sytuacji nie jest CSKA. Kondycja tego zespołu jest zdecydowanie lepsza, ale i tak - jak potwierdził Andriej Watutin - dysponować będą budżetem aż o 30 procent mniejszym.
Sezon 2009/10 będzie zapewne regresem w wykonaniu tej ekipy. Sternicy zatrudnili bowiem na stanowisko pierwszego trenera Jewgienija Paszutina, który ma skompletować młody, oparty głównie na rosyjskich koszykarzach, zespół. Już teraz głośno mówi się o odejściu Johna Roberta Holdena, Nikosa Zisisa, czy też Matjaza Smodisa. Niepewna jest także przyszłość Ramunasa Siskauskasa. Wiele więc wskazuje na to, że powtórzyć wyniki chociażby Dusko Ivanovicia będzie niezwykle trudno.
Czyżby nadchodził początek końca dominacji CSKA w Rosji i Europie?