Нови век и нови успеси
После пет година Звезда је 2000. освојила титулу и изборила се за први наступ у реформисаним квалификацијама за Лигу шампиона, у којима је после победа над КИ Клаксвиком и Торпедом из Кутаисија играла са кијевским Динамом. Испоставиће се да је то била најбоља прилика у првих пет покушаја да се домогнемо елитног такмичења – у Кијеву је било 0:0, у Београду је Звезда водила 11 минута, али је гол у гостима Валентина Бјалкевича пресудио. Звезда се преселила у Куп УЕФА, где је са успехом надиграла Лестер Сити (иако је реванш игран у Бечу), а затим се добро носила са Селтом, док се није испоставило да су процедуралном грешком у састав убачена два играча који немају право наступа у Вигу.

Уследио је нови покушај у Лиги шампиона, победа над Омонијом, па 0:0 и 0:3 са Бајером из Леверкузена, каснијим финалистом. У Купу УЕФА Звезда је доживела тежак неуспех, јер је у првом колу испала од нејаке екипе ЦСКА Кијев.

Следе поново две сезоне у Купу УЕФА, прва гостовања у Казахстану и Молдавији, победе над Кјевом и Оденсеом, а затим неуспеси у дуелима са њиховим суседима Лациом и Росенборгом. Против Норвежана Звезда је имала сјајну прилику да дочека пролеће – играча више у Трондхајму и меч завршен без голова, али је у Београду једини погодак постигао Братбак.

Нова титула 2004. године и сјајан припремни период подмлађене екипе донели су велике амбиције, а две београдске победе над Јанг Бојсом и ПСВ-ом само су их појачале. Дан пред реванш у Ајндховену повредио се Никола Жигић и Звезда се суочила са озбиљним проблемом. Неискусна екипа лоше је реаговала, ПСВ је реванш добио резултатом 5:0 (најубедљивији пораз у европској историји клуба), што ће оставити дубок траг на целу генерацију. Још увек у шоку наша екипа поражена је у Санкт Петербургу од Зенита 4:0 и опростила се и од Купа УЕФА, а са клупе је и трећи пут отишао Љупко Петровић.

У нови формат Купа УЕФА Звезда је успешно крочила 2005. године – у квалификацијама је декласиран хрватски Интер, у првом колу голом у гостима побеђена Брага, па је Звезда добила групу са Базелом, Трумсеом, Ромом и Стразбуром. Против Швајцараца Звезда је играла без публике, али је повела, играла добро и – изгубила голом три минута пре краја. У Норвешкој очекивала се победа, али је доживљен убедљив пораз. Када је изгледало да наде у пролазак нема наша екипа је убедљиво победила Рому уз бриљантан наступ Николе Жигића, па је у последњем колу победа у Стразбуру гарантовала европско пролеће. У Алзасу је утакмица почела одлично, Звезда је у последњих 10 минута ушла са предношћу од 2:0, али су две велике грешке одбране омогућиле тинејџеру Гамеру да се прослави и десет секунди пре краја меча нанесе тежак ударац нашем клубу.
Европска Звезда
У историји европских купова дугој више од шест деценија само два клуба са Истока носила су наслов шампиона континента – румунска Стеауа и наша Црвена звезда. Звездин грб заувек ће остати на шпици програма посвећених Лиги шампиона, али успеси из 1991. само су врх леденог брега састављеног од сјајних резултата многих Звездиних генерација.

Иако је иза нашег клуба петнаест релативно несупешних година у европским оквирима, јер је Звезда последњи пут дочекала пролеће у Европи још 1992. године, место на листи најуспешнијих клубова у историји евро-купова нико нам не може одузети.

У сезону 2007/2008 Црвена звезда је ушла као шеснаести тим на вечној европској листи, непосредно иза кијевског Динама, а испред Селтика и ПСВ Ајндховена. Резултати из текуће сезоне могу нас подићи до петнаестог или спустити до осамнаестог места.

Звезда је осим освајања Купа шампиона и Интерконтиненталног купа 1991. године играла у финалу Купа УЕФА дванаест година раније, пласирала се укупно шест пута у полуфинала европских купова, а петнаест пута стигла међу осам најбољих. Иако не спада у службена такмичења УЕФА, Средњоевропски куп некада је имао велики престиж,а Звезда га је освојила 1968. године.