בעונת 2002/2003 יצר מלדיני יחד עם קאפו, אלסנדרו נסטה ואלסנדרו קוסטקורטה רביעיית הגנה שעוד תיחשב לאחת מן הטובות בהיסטוריה. את אותה עונה סיים מלדיני במקום השלישי בליגה ועם זכייה בפעם הראשונה בקריירה בגביע האיטלקי. מלדיני ערך את הופעתו ה-500 בליגה האיטלקית ב-15 במרץ 2003, וזכה בליגת האלופות פעם נוספת באותה עונה. בפעם הראשונה בהיסטוריה הגמר היה כל-איטלקי: מילאן התמודדה מול יובנטוס, שאותה ניצחה 3-2 בפנדלים לאחר שלא הובקעו שערים לאורך 120 דקות. מלדיני זכה לראשונה בליגת האלופות בתור קפטן בדומה לאביו, אשר זכה גם הוא 40 שנים קודם לכן בליגת האלופות כקפטן מילאן, גם כן על אדמת אנגליה. מלדיני זכה בתואר שחקן המשחק, ובפעם הראשונה בקריירה שלו הוא זכה למקום בנבחרת השנה של אופ"א, והגיע בפעם השנייה בקריירה שלו למקום השלישי בפרס כדור הזהב.
בעונת 2003/2004 הפסידה מילאן בפנדלים ליובנטוס בסופר קאפ האיטלקי. באליפות העולם לקבוצות נגד בוקה ג'וניורס הפסידה פעם נוספת בפנדלים, אך הצליחה לנצח את פורטו ולזכות בסופר קאפ האירופי. מילאן שבה ולקחה את אליפות איטליה כשמלדיני הוא הקפטן, אולם הודחה מהגביע האיטלקי בחצי הגמר. באותה עונה הגיעה מילאן רק לרבע גמר ליגת האלופות, שם הודחה על ידי דפורטיבו לה קורוניה. באפריל 2004 נמנה מלדיני ברשימת השחקנים הטובים ביותר של 50 השנים האחרונות של פיפ"א. בנוסף לכך הוא נמנה ברשימת פיפ"א 100 - רשימה של 125 הכדורגלנים הטובים ביותר שיצר פלה. בסיום העונה מלדיני נבחר לשחקן ההגנה של הסרייה א'.
מלדיני החל את עונת 2004/2005 בהנפת הסופר קאפ האיטלקי לאחר שמילאן ניצחה את לאציו. מילאן סיימה שנייה ליובנטוס באותה עונה בליגה, ואף הגיעה לגמר ליגת אלופות פעם נוספת, שבו הפסידה לליברפול בפנדלים לאחר שהובילה 3-0 במחצית. משחק זה נחשב לגמר ליגת האלופות הגדול בהיסטוריה. באותו גמר מלדיני קבע שיא חדש, כאשר כבש כבר בדקה הראשונה של המשחק. זהו שיא לשער המהיר ביותר בגמר ליגת האלופות. בנוסף לכך מלדיני הפך לשחקן המבוגר ביותר שכובש בגמר ליגת האלופות. בסוף אותה עונה מלדיני נבחר בפעם השנייה בקבוצת השנה של אופ"א והוא אף נבחר בקבוצת השנה של פיפ"א.
בעונת 2005/2006 סיימה מילאן פעם נוספת שנייה ליובנטוס בליגה האיטלקית. בליגת האלופות הגיעה מילאן לחצי הגמר, שבו הודחה על ידי הזוכה ברצלונה. באותה עונה כבש מלדיני בפעם הראשונה והיחידה שלו צמד שערים במשחק נגד רג'ינה קלצ'ו. ב-25 בספטמבר 2005 שבר מלדיני את שיאו של דינו זוף והפך לשחקן עם מספר ההופעות הרב ביותר בליגה האיטלקית עם 571 הופעות, כששבוע לפני הוא ערך את הופעתו ה-800 בכל המסגרות עבור מילאן.
בעונת 2006/2007 עזר מלדיני למילאן להגיע למקום הרביעי בליגה האיטלקית, כשהוא מוביל אותם למיקום שאיפשר עלייה לליגת האלופות. מלדיני שיחק את משחקו ה-600 בליגה האיטלקית ב-13 במאי 2007. באותה עונה מלדיני הוביל את מילאן כקפטן לגמר ליגת האלופות שלישי בתוך שש שנים, שבו מילאן גברה על ליברפול 2-1, כך השיגה הקבוצה נקמה בליברפול, שניצחה אותה בגמר ב-2005. בגיל 37 מלדיני הפך לקפטן המבוגר ביותר שמניף את גביע ליגת האלופות. מלדיני השתתף ב-8 גמרים של ליגת האלופות, דבר שנשבר רק על ידי פרנסיסקו חנטו מריאל מדריד. מלדיני זכה חמש פעמים בליגת האלופות, מתוכן פעמיים כקפטן. מלדיני זכה בסוף אותה עונה בתואר שחקן ההגנה של אירופה.
ב-2007 זכתה מילאן בסופר קאפ האירופי כשניצחה את סיביליה. מלדיני הפך לקפטן האירופי הראשון שמניף את תואר אליפות העולם למועדונים לאחר שמילאן גברה על בוקה ג'וניורס.
בסוף אותה עונה הודיע מלדיני כי יפרוש ממשחק אך דחה את ההחלטה לסיום עונת 2008/2009.
2008 - 2009: העונה האחרונה והפרישה.
ב-16 בפברואר 2008 ערך מלדיני את הופעתו ה-1,000 במסגרת רשמית כשרק פיטר שילטון, השוער האנגלי, שיחק יותר משחקים ממנו. מלדיני שיחק את משחקו האחרון בליגת האלופות ב-4 במרץ 2008 בהפסד של מילאן לארסנל, שהדיחה את מילאן כבר בשלב שמינית הגמר. ב-2008 זכה מלדיני בפרס תואר המצוינות של פיפ"א. זהו התואר הגבוה ביותר שפיפ"א מחלקת. בנוסף לכך הוא זכה בפרס ג'אצ'ינטו פאקטי, פרס אשר מוענק לשחקן אשר הראה יכולת טובה לאורך הקריירה ושמר על חוקי המשחק ההגון. ב-28 באוגוסט 2009 העניקה אופ"א למלדיני פרס על הקריירה שלו.
ב-18 באפריל 2009 הודיע מלדיני כי יפרוש ממשחק פעיל בסוף העונה. ב-17 במאי 2009 ערך מלדיני את הופעתו ה-900 במדי מילאן בכל המסגרות. משחקו האחרון בסן סירו היה ב-24 במאי 2009 בהפסד של מילאן לרומא, באותו משחק מלדיני זכה לתשואות רבות וכבוד רב מהקהל. הופעתו האחרונה במילאן ובליגה האיטלקית הייתה ב-31 במאי 2009, בניצחון של מילאן 2-0 על פיורנטינה.
בעקבות פרישתו מילאן הפרישה את מספר החולצה שלבש, 3, אך הודיעה כי אם יום אחד בנו ישחק בשורותיה, הוא יזכה ללבוש את המספר שלו, כפי שמלדיני לבש את מספר 3 שהיה מזוהה עם אביו.
בשנת 2019 ערך דניאל מלדיני, בנו של פאולו, את הופעתו הראשונה במדי מילאן.
נבחרת איטליה.
תחילת הקריירה ומונדיאל 1990.
בשנת 1986 זומן מלדיני לנבחרת איטליה עד גיל 21 על ידי מי שהיה אז מאמן הנבחרת, אביו, צ'זארה מלדיני, והוא ערך את הופעתו הראשונה בנבחרת עד גיל 21 ב-12 בנובמבר 1986. מלדיני ערך 12 הופעות וכבש 2 שערים בשנתיים שבהן שיחק בנבחרת הצעירה, כשהשער הראשון אותו כבש היה ב-11 בפברואר 1987 בניצחון 2-1 על נבחרת פורטוגל. מלדיני הגיע עם נבחרת איטליה עד גיל 21 למקום השני ביורו הצעירות לשנת 1986, שם הפסידה איטליה לספרד. שנתיים לאחר מכן הוא שיחק שוב ביורו הצעירות לשנת 1988, שם איטליה הודחה כבר בסיבוב הראשון.
מלדיני ערך את הופעתו הראשונה בנבחרת הבוגרת בגיל 19 ב-31 במרץ 1988. מלדיני זומן למשחקים האולימפיים לשנת 1987 אף על פי שלא לקח חלק בהם. מלדיני שיחק בכל המשחקים ששיחקה נבחרת איטליה ביורו 1988, שבו הגיעה עד לחצי הגמר והודחה על ידי נבחרת רוסיה.
הופעתו הראשונה במונדיאל הייתה במונדיאל 1990 אשר נערך באיטליה. מלדיני השתתף בכל שבעת המשחקים ששיחקה נבחרתו. מלדיני עזר לנבחרת לצבור 5 ניצחונות רצופים ובנוסף לכך הצליח לשמור על שער נקי באותם 5 משחקים, מה שמהווה שיא מונדיאל. מלדיני וחבריו לחוליית ההגנה ספגו לבסוף שער בחצי גמר המונדיאל נגד ארגנטינה, וזאת לאחר זמן שיא של 518 דקות ללא ספיגה במונדיאל. המשחק הסתיים בהפסדה של איטליה לארגנטינה בפנדלים. עם זאת, היא הצליחה לנצח את נבחרת אנגליה בקרב על המקום השלישי. נבחרת איטליה סיימה את הטורניר כקבוצה ההגנה הטובה ביותר, לאחר שספגה שני שערים בלבד לאורך כל הטורניר, ומלדיני שובץ בקבוצת הטורניר.
גמר מונדיאל 1994 ומינוי לקפטן.
שערו הראשון של מלדיני בנבחרת איטליה הגיע במשחק ה-44 שלו בנבחרת, ב-20 בינואר 1993. מלדיני וחבריו לנבחרת איטליה כשלו להעפיל ליורו 1992.
במשחקי מוקדמות מונדיאל 1994 מונה מלדיני לקפטן זמני של נבחרת איטליה. במהלך מונדיאל 1994 שיחק מלדיני בכל שבעת המשחקים של נבחרתו, והצליח לעזור להגנת איטליה לשמור על שער נקי בארבע משחקים. הוא הוביל את הנבחרת לגמר, כשבמהלך הטורניר מלדיני שיחק גם כבלם וגם כשחקן אגף. למרות פציעות רבות של כמה שחקני מפתח מההגנה האיטלקית במהלך הטורניר, מלדיני עזר לנבחרתו לשמור על רשת נקייה במשחק הגמר נגד נבחרת ברזיל, אך בסיומו הפסידה לברזיל בפנדלים. מלדיני שובץ בקבוצת הטורניר פעם נוספת, וזאת 32 שנה אחרי שגם אביו זכה לאותו תואר במונדיאל 1962.
לאחר פרישתו של פרנקו בארזי בשנת 1994, מונה מלדיני לקפטן הנבחרת באופן סופי. ביורו 1996 נחלה נבחרת איטליה אכזבה, כשהודחה כבר בשלב הבתים עם ארבע נקודות. הבית של איטליה באותו יורו כונה "בית המוות", כששתי פייבוריטיות שיחקו יחד איתה, נבחרת גרמניה ונבחרת צ'כיה. מלדיני שיחק בכל שלושת המשחקים של הנבחרת בשלב הבתים. את מונדיאל 1998 בצרפת החלה נבחרת איטליה בסערה כשסיימה ראשונה בבית. בשלב שמינית הגמר איטליה ניצחה את נבחרת נורווגיה וברבע הגמר פגשה את נבחרת צרפת, והפסידה לה בפנדלים. איטליה הודחה מהמונדיאל בפעם השלישית ברציפות בפנדלים.
יורו 2000 והמונדיאל הרביעי והאחרון.
מלדיני ערך את הופעתו ה-100 בנבחרת ב-28 באפריל 1999. ביורו 2000 הגיעה נבחרת איטליה עד לגמר, שם התמודדה מול אלופת העולם נבחרת צרפת והפסידה בתוספת הזמן. מלדיני שיחק בכל ששת המשחקים של נבחרת איטליה בטורניר. איטליה סיימה בראשות הבית שלה לאחר שניצחה כל משחק. מלדיני, ששיתף פעולה עם פאביו קנבארו ואלסנדרו נסטה בהגנה, סייע לנבחרת לספוג רק שני שערים לאורך הטורניר עד הגמר. בחצי הגמר מלדיני וחבריו הצליחו לשמור על שער נקי ולהוביל את המשחק לפנדלים, שם, על אף שמלדיני פיספס את אחד הפנדלים, איטליה ניצחה בדו-קרב הבעיטות 3-1. מלדיני שובץ בקבוצת הטורניר.
ב-7 באוקטובר 2000, בניצחונה של נבחרת איטליה במוקדמות מונדיאל 2002, עקף מלדיני את דינו זוף והפך לשחקן עם הכי הרבה הופעות בנבחרת איטליה עם 113 הופעות. המונדיאל הרביעי של מלדיני והשני שלו כקפטן היה מונדיאל 2002. מלדיני שיחק בכל ארבעת המשחקים של איטליה בטורניר, כשהוא שומר על שער נקי במשחק הפתיחה נגד אקוודור. איטליה הודחה כבר בשמינית הגמר לאחר שנותרה בעשרה שחקנים.