Početak 21. veka je obeležio šlag na torti dominacije Bečeja, čiji su igrači osvojili 2000-te titulu prvaka Evrope, a ogromnu zaslugu za to imaju i Partizanovi bivši igrači i treneri, Vlaho Orlić, Aleksandar Šoštar i Predrag Zimonjić.
U septembru 2001. Partizan preuzimaju Igor Milanović i Aleksandar Šoštar i privremeno klub stavljaju na noge.
U sezoni 2001-2002 VK Partizan osvaja posle 7 godina čekanja, duplu krunu i time prekida 6-šnju dominaciju Bečeja u domaćem vaterpolu.
Klub je sa trenerskog mesta predvodila igračka legenda, Dejan Udovičić.
Imao je na raspolaganju od starijih igrača Nikolu Kuljaču, Borisa Popovića i Mihajla Koroliju.
U međuvremenu je stasala nova generacija na Banjici, predvođena Vanjom Udovičićem i igrali su u njoj još i Slobodan Nikić, Živko Gocić, Miloš Korolija, Đorđe Filipović, Milan Tičić, Nemanja Marjan… Iz Zvezde je doveden Slavko Gak, a iz Vojvodine Marko Ćuk (stariji brat, Miloša Ćuka).
Na kraju te sezone iz kluba odlaze u Niš, Kuljača i MihAjlo Korolija a dolaze iz Vojvodine tada još juniori braća Pijetlović i Rađen. Prvom timu je priključen i Filip Filipović koji je imao tek 15 godina tada. Bilo je planirano da ova generacija najkasnije do 2005. ili 2006. konačno osvoji tu 7. titulu prvaka Evrope.
Ali leta 2003. su došli dugovi na naplatu. Između tri opcije, izabrana je ona najbolja, raspušten je veći deo prvog tima a većinu tih igrača su pokupili Jadran, Primorac i Niš. Od nešto starijih igrača ostali su samo Miloš Korolija i Đorđe Filipović.
Sledeće sezone je Partizan imao najmlađu ekipu u svojoj istoriji u kojoj su dvojica nastarijih igrača imali po 22 godine, a svi ostali ne više od 20. To je naravno rezultiralo osvajanjem tek četvrtog mesta u prvenstvu, ispadanjem u polufinalu kupa i osvajanjem 1 boda u Evroligi.
Od sezone 2004-2005 počinje konsolidacija kluba kada je Rajfajzen banka postala generalni sponzor.
U Partizan se vraćaju Jugoslav Vasović i Denis Šefik (koji doduše u svom prvom boravku u klubu su još bili mladi igrači i nisu ostavili neki trag) ali i Danilo Ikodinović. Doveden je i najbolji slovenački igrač, Matej Nastran.
Ipak sve ovo nije bilo dovoljno da se u naredne dve godine prekine dominacija Jadrana. Partizan je međutim za razliku od predhodne dve sezone dolazio do finala plej ofa i domaćeg kupa.
Napravljen je i ogroman pomak u evro okvirima, jer se 2005. stiglo do finala Len kupa gde je Partizan poražen od Savone koju su predvodili Kašaš i Šapić. Naredne 2006. posle dosta godina crno beli prave i zapažen rezultat u Evroligi, igrao je Partizan u 1/4 finalu i izgubio od Juga koji je kasnije i osvojio ovo takmičenje.
Leto 2006-te donosi raspad državne zajednice SCG a i automatski Partizan ostaje bez konkurencije u domaćim okvirima.
U klub se vraća Nikola Kuljača a iz Jadrana stiže jedan od najvećih talenata svetskog vaterpola, Andrija Prlainović. Prvom timu je priključen i Stefan Mitrović.
Na Banjici je već polako stasavala jedna nova generacija, predvođena nešto starijim Korolijom i mlađima Filipovićem, Milanom Aleksićem, Rađenom, braćom Pijetlović.
U Partizan su se narednih godina vraćali Živko Gocić, Vladimir Vujasinović, Slobodan Soro i Slavko Gak. Dovođene su velike zvezde američkog i grčkog vaterpola, Rajan Bejli i Teodoras Hadžiteodoru.
Iz Vojvodine su došli, Miloš Ćuk i Branislav Mitrović, iz Jadrana Aleksandar Radović a iz Primorca vaterpolo vunderkind Dušan Mandić.
Sve ovo je uslovilo da Partizan u narednih 6 godina osvoji isto toliko duplih kruna, kao i dva trofeja u novoformiranom takmičenju – evrointer ligi.Stizalo se i do F4 Evrolige dva puta, gde je osvajano treće mesto kao i do dva 1/4 finala.
Međutim na ono najznačajnije, tj osvajanje po 7. put titule prvaka Evrope se čekalo do 2011. Tada je Partizan pobedio verovatno najskuplju ekipu u istoriji vaterpola, Pro Reko i to na njegovom terenu, može se reći sa laganih 11-7.
stoje – Prlainović, Korolija, Aleksić, Radović, Rađen, Vujasinović, Soro i Dedović
čuče – Šaponjić, Avramović, Živojinović, Ćuk, Pijetlović, Hadžiteodoru i Mitrović
Taj 3,5 decenije sanjani san, su ostvarili Igor Milanović kao trener a od igrača Vladimir Vujasinović, Slobodan Soro, Andrija Prlainović, Duško Pijetlović, Aleksandar Radović, Milan Aleksić, Stefan Mitrović, Miloš Korolija…
Par meseci posle toga Partizan osvaja i svoj drugi Superkup Evrope, pobedom u finalu nad Savonom i to na njenom bazenu i bez četiri igrača koji su pre toga uzeli Ligu šampiona.
Na kraju sezone 2011-2012 VK Partizan je imao osvojenih 62 trofeja, plus još 8 nezvaničnih. Tri finala u Kupu šampiona, pet trećih mesta u Kupu šampiona i Ligi šampiona, dva polufinala i pet četvrtfinala u Kupu šampiona i Ligi šampiona, kao i po jedno finale u Len kupu i Superkupu Evrope.
