Már-már úgy tűnt, hogy Maldini nem is tud rosszul játszani, hiszen a későbbiekben is mind a Milanban, mind pedig az olasz válogatottban kiemelkedőt nyújtott.
Az 1995-96-os bajnokságban megnyerte ötödik olasz bajnoki címét, az 1996-os Európa-bajnokság előtt ő lett az olasz válogatott állandó csapatkapitánya, és a Nemzetközi Labdarúgó-szövetség, a FIFA 1995-ben őt szavazta meg a világ második legjobb labdarúgójának.
Szinte törvényszerű volt, hogy hullámvölgynek kell következnie, és így is történt: az 1996-os kontinensviadalon saját magához képest gyenge teljesítményt nyújtott, és később a klubcsapatában sem találta régi formáját. Persze a Milan sem volt már ugyanaz a gárda, mint pár évvel korábban: többen távoztak a klubtól, és az újonnan érkezett sztárokból nem alakult ki egységes csapat. Edzők jöttek és mentek a klubnál, Óscar Tabárezt előbb Sacchi váltotta, majd pedig Capello próbálta visszahozni a sikereket, kevés eredménnyel.
A Milan előbb 11. lett a bajnokságban, majd egy évre rá csak a tizedik helyen végzett. Pedig Baresi 1997-es visszavonulását követően Capello Maldinit tette meg csapatkapitánynak, ám Paolo ekkor még nem tudta igazán átérezni a felelősséget. Kicsit a fejébe szállt a dicsőség, mindig másban kereste a hibát akkor is, amikor nem ment neki a játék, szinte mindegyik csapattársával összeveszett.
Az sem tett jót neki, hogy 1996-től édesapja, Cesare lett az olasz szövetségi kapitány, hiszen egyre inkább elterjedtek a rosszindulatú pletykák, melyek szerint csak apja miatt kihagyhatatlan a válogatottból. Az 1998-os világbajnokságon le is szerepelt a talján gárda, és bár természetesen nem esett neki jól, hogy apjának a fiaskó után felmondtak, minden bizonnyal megkönnyebbülést jelentett a számára, hogy Dino Zoff lett a szövetségi kapitány.