המעבר למילאן:
בקיץ 1999, המליצו המנהל הראשי של מילאן ושחקן העבר רובן בוריאני, להעבירו למילאן. העסקה אכן יצאה לפועל, והוא חתם במילאן תמורת 8 מיליון יורו. הוא זכה בחולצה מספר 8, אשר נלחם למענה מלכתחילה, על מנת להפוף לאהוב הקהל.
מילאן:
תקופת השיא:
את משחק הבכורה שלו, ערך גאטוסו ב-15 בספטמבר 1999, במשחק חוץ בליגת האלופות נגד צ'לסי, שהסתיים ב-0-0. עונת 2002/2003 הייתה הטובה ביותר מבחינת השחקן, כאשר מילאן זכו בליגת האלופות נגד יובנטוס, ובגביע האיטלקי נגד רומא. ב-2003/2004, כאשר זכתה מילאן בסקודטו ה-17, שיחק גאטוסו ב-33 מתוך 34 המשחקים שהיו למילאן בליגה באותה עונה (עד 2004 היו 18 קבוצות בסרייה א'). בעונה לאחר מכן, הוא שיחק ב-45 משחקים של מילאן בכל המפעלים, כולל משחק הגמר המביש נגד ליברפול (2005). בעונות 2005-2006, שיחק גאטוסו ב-35 משחקים, ואף כבש 3 שערים בליגה האיטלקית, שיחק 11 מתוך 12 משחקים בליגת האלופות וגם זכה בגביע הנוכחות באיטליה. בחודש דצמבר 2006, היה גאטוסו במקום ה-14 של כדור הזהב. ב-23 במאי, הוא זכה עם מילאן בליגת האלופות נגד ליברפול, שנתיים לאחר התבוסה הגדולה. ב-16 בדצמבר הוא זכה באליפות העולם למועדונים, עם נצחון 4-2 בגמר נגד בוקה ג'וניורס הארגנטינאית.
הפציעה והמאמנים החדשים:

בקיץ 2008, היה קרוב מאוד לעבור לבאיירן מינכן הגרמנית, אך בסוף אדריאנו גליאני שיכנע אותו להישאר במילאן, והוא נשאר. ב-7 בדצמבר 2008, במהלך משחק נגד קטאניה, נפצע גאטוסו, אך עדיין היה על המגרש לאורך כל 90 הדקות. תוצאות ה-MRI, שנעשו יומיים לאחר מכן, חשפו פציעה ברצועה הצולבת הקדמית, בברך הימנית. ב-15 בדצמבר, זמן התאששותו, נאמד בכ-6 חודשים. קצת יותר מ-6 חודשים לאחר שנפצע, חזר גאטוסו למגרשים ב-10 במאי 2009, במשחק נגד יובנטוס, שבו נשאר על הספסל עד סוף המשחק. הוא חזר לשחק יומיים מאוחר יותר, במשחק ידידות בטירנה, נגד הלאומנות האלבנית. את המשחק התחרותי הראשון לאחר החזרה מהפציעה, שיחק גאטוסו ב-31 במאי 2009, אחרי 5 וחצי חודשים מהניתוח, במשחק האחרון לעונת 2008/2009, נגד פיורנטינה, שבו ניצחה מילאן 2-0. במהלך עונת 2009/2010, גאטוסו כמעט ולא שותף (יחסית לפעמים הקודמות), זאת בעקבות הגעתו של לאונרדו. גאטוסו שיחק באותה עונה 24 משחקים: 22 בליגה, אחד בגביע האיטלקי ואחד בליגת האלופות. בעונת 2010/2011, עם הגעתו של המאמן החדש, מסימיליאנו אלגרי, גאטוסו חזר להיות שחקן הרכב. ב-21 בפבואר, הושעה גאטוסו ל-4 משחקים במסגרת ליגת האלופות, זאת בעקבות מה שקרה במשחק שמינית הגמר של ליגת האלופות נגד טוטנהאם, כאשר השחקן תקף את ג'ו ג'ורדן, עוזר מאמנה של טוטנהאם. ב-5 במרץ, כבש גאטוסו שער מנצח, נגד יובנטוס בסטאדיו אולימפיקו בטורינו. זהו שער ראשון שלו לאחר 3 עונות. ב-7 במאי, הוא זכה באליפות ה-2 שלו עם מילאן, שלושה משחקים לפני תום העונה בסטאדיו אולימפיקו ברומא לאחר 0-0. במשחק האחרון של מילאן בסן סירו, התקיים משחק ההכתרה שלה, גאטוסו כבש שער אחד במשחק, שנגמר 4-1 למילאן על קליארי.
קריירה בנבחרת:

גאטוסו שיחק לראשונה במדי נבחרת איטליה עד גיל 18, בעונת 1995/1996. יש לו 14 הופעות ו-3 שערים.
גאטוסו שיחק לראשונה במדי נבחרת איטליה עד גיל 21, בעונת 1998/1999. יש לו 21 הופעות ושער אחד.
גאטוסו עשה את הופעת הבכורה שלו בנבחרת הבוגרת, עם המאמן דינו זוף, ב-23 בפבואר, שנת 2000, בגיל 22, במשחק ידידות של איטליה נגד שוודיה, שנגמר בהפסד 1-0 והמשחק נערך בסיציליה. ב-15 בנובמבר, 2000, השיג גאטוסו את השער היחיד שלו בנבחרת, עם בעיטה מחוץ לרחבה, במשחק ידידות נגד אנגליה שנערך בדלה אלפי בטורינו. עם טרפטוני כמאמן איטליה, לקח גאטוסו חלק באירוע גדול ראשון עם הנבחרת הלאומית, מונדיאל 2002, שם הוא ערך 2 הופעות. עם מרצ'לו ליפי כמאמן, זומן גאטוסו למונדיאל 2006, שם הוא הפך לאלוף עולם, ב-9 ביולי 2006, במשחק הגמר נגד צרפת, שבו ניצחה איטליה 5-3 בפנדלים (1-1 בזמן החוקי). הוא לקח חלק ביורו 2008, שנערך באוסטריה ושוויץ, שם הוא החמיץ את משחק רבע הגמר נגד ספרד (שבו גם הודחה איטליה), עקב השעיה. ב-19 בנובמבר, 2008, היה גאטוסו קפטן הנבחרת בפעם הראשונה בחייו, כאשר בדקה ה-61, במשחק ידידות נגד יוון, הוחלף הקפטן, פאביו קנאבארו וגאטוסו קיבל את סרט הקפטן. הוא זומן ע''י ליפי לגביע הקונפדרציות שנערך בדרום אפריקה, וזאת למרות שהוא חזר מפציעה קשה של חצי שנה בברך. הוא גם זומן למונדיאל 2010, שנערף בדרום אפריקה, וסיכם את הקריירה שלו בנבחרת הלאומית ב-24 ביוני 2010, לאחר ההפסד 3-2 לסלובקיה, וההדחה המוקדמת בשלב הבתים.
חייו האישיים:
גאטוסו נשוי למוניקה רומאנו (אישה סקוטית ממוצא איטלקי), אותה הכיר כששיחק עבור ריינג'רס, במשחק תערוכה בטורונטו, קנדה. יש להם בת, גבריאלה (בת 7 - נולדה ב-20 ביוני 2004), ובן, פרנצ'סקו (בן 4 - נולד ב-8 בנובמבר 2007). מוניקה היא אחותה של כתבת '''GMTV's לוס אנג'לס'', קרלה רומאנו. בינואר 2010, פתח גאטוסו חנות דגים בעיר גאלארטה, עיר שבה חי במשך 8 שנים. הוא טען כי ההשראה שלו לאוכל היא המטבח הבריטי, שאותו ראה ואכל, כאשר שיחק בריינג'רס. ככל הנראה, אחד המאכלים האהובים עליו הוא האגיס מטוגן (מאכל סקוטי מסורתי). הוא שמר את המתכונים עליו, באלבום לצד תיבה של מכתבי אהבה במגירה העליונה. גאטוסו גם מופיע על עטיפות של משחקי ווידאו, כולל ''FIFA Streat 3''.