Lata 2001-2010

1 lipca 2001 usunięto z nazwy klubu markę byłego sponsora i powrócono do nazwy ASPN CWKS „Legia” Warszawa SSA.
W sezonie 2001/02 piłkarze Legii pod opieką Serba Dragomira Okuki zdobyli siódmy tytuł mistrzowski, dzięki remisowi 0:0 z Odrą Wodzisław w Warszawie, a także Puchar Ligi Polskiej (3:0 i 1:2 z Wisłą Kraków). W Lidze Mistrzów Legia przegrała jednak w eliminacjach z FC Barceloną, a w pucharze UEFA odpadła w drugiej rundzie. W pierwszej rundzie Legia pokonała FC Utrecht 4:1 i 3:1.
Legioniści skończyli rozgrywki w 2003 tuż za podium. Niedługo po tym nastąpiła zmiana nazwy na KP „Legia” Warszawa SSA i jeszcze tego samego dnia trenerem stołecznego klubu został Dariusz Kubicki.
Wykupienie klubu przez Grupę ITI Holdings SA zostało entuzjastycznie przyjęte przez kibiców, a Legia zajęła drugie miejsce w lidze. Następny rok także nie należał do udanych, stołeczny zespół zajął trzecie miejsce w lidze.
Sezon 2005/06 był wyjątkowy w historii klubu. Legia odpadła z Pucharu UEFA w II rundzie eliminacji (0:1 w Warszawie i 2:4 w Zurychu z miejscowym FC Zürich) i zaliczyła słaby początek ligi. Mimo to w 90-lecie istnienia drużyny Legioniści zdobyli ósme mistrzostwo Polski po wygranym 1:0 meczu z Górnikiem w Zabrzu^. Po przyjściu nowego trenera Dariusza Wdowczyka, Legioniści odrobili siedem punktów straty do Wisły Kraków i wyszli na prowadzenie w lidze. Po tych sukcesach Rada Miasta Stołecznego Warszawy podjęła decyzję o sfinansowaniu modernizacji stadionu Legii poprzez budowę trzech nowych trybun i rozbudowę trybuny krytej.
W kolejnym sezonie Wojskowi odpadli z rozgrywek o Puchar Polski w 1/16 finału, ulegając czwartoligowej Stali Sanok, a w lidze uzyskali trzecią lokatę. Rok 2007 przyniósł zmianę herbu. Klub nie doszedł do porozumienia z CWKS, który miał prawa do poprzedniego logo. Władze klubu zarejestrowały swój znak, zbojkotowany przez kibiców, ponieważ nie przypominał on w niczym dawnego znaku (mimo podobnych kolorów oraz litery „L” miał inny kształt i ułożenie barw). Ostatecznie nie został on wprowadzony w życie i ustalono, że herbem zostanie modyfikacja pierwszego herbu, z białą literą „L” na czarnej tarczy. Obecny kształt różni się od historycznego i przypomina trójkąt, a nie pierwotną tarczę herbową.