סגנון ההארד רוק ניכר עוד יותר באלבום הבא, "Risk", משנת 1999. היקף מכירותיו היה נמוך יחסית. זמן קצר לאחר שחרורו, פרש מרטי פרידמן מהלהקה והוחלף על ידי אל פיטרלי. הלהקה חיפשה דרך לסיים את החוזה עם חברת ההקלטות קפיטול רקורדס, לכן הוציאה לאור אלבום אוסף בשם "Capitol Punishment: The Megadeth Years". האוסף כלל בתוכו שני שירים חדשים, שעליהם מגאדת' התחייבו לפי החוזה עם קפיטול.
שנות ה-2000.
בשנת 2001, מגאדת' חתמו על חוזה עם חברת התקליטים סנקצ'וארי רקורדס, ולאחר זמן קצר הוציאו אלבום חדש, בשם "The World Needs a Hero" שהוכרז על ידי המעריצים כחזרה מוצלחת לשורשי הת'ראש המוכרים של הלהקה.
ב-3 באפריל 2002, מאסטיין הכריז בפומבי על עזיבתו את הלהקה. הסיבה הרשמית הייתה פגיעה עצבית בידו השמאלית. החברים האחרים החליטו לפרק עקב זאת את הלהקה. הדבר נראה כסופה של להקה בת כמעט 20 שנה.
בהדרגה, הפיזיותרפיה עזרה לידו של מאסטיין להחלים. לאחר שלמד מחדש לנגן על הגיטרה, הוא כתב את אלבום הסולו הראשון שלו ותכנן הנפקה מחודשת של הקטלוג של מגאדת'. בשנת 2004 הוא יצר קשר עם חברי הלהקה המוקדמת עם בקשה לעזרה בהקלטת האלבום החדש שלו שנקרא במקור "Blackmail The Universe" (שמו של השיר הפותח את האלבום), אך שמו שונה ל-"The System Has Failed" (ביטוי מתוך השיר השלישי, Kick The Chair שמבקר את מערכת המשפט). בגלל ההסכם עם חברת ההקלטות שלפיו מגאדת' מתחייבת לאלבום נוסף, האלבום היה חייב להשתנות מאלבום סולו לאלבום האחרון של מגאדת'. האלבום הוקלט עם ויני קוליוטה על התופים, כריס פולאנד (שניגן עם מגאדת' בשנות ה-80) על גיטרה מלווה וג'ימי לי סלואס על גיטרת הבס. כמו שדייב מאסטיין אמר: "מגאדת' באיטיות קמה לתחייה".
לאחר צאת האלבום בתחילת יולי 2004, "The System Has Failed" זכה לביקורות טובות כאלבום שמחזיר את מגאדת' ל"תור הזהב" מסוף שנות ה-80 ותחילת שנות ה-90, ואף הגיע למקום ה-18 ברשימת הבילבורד האמריקני. לאחר הוצאת האלבום הוחלפו פולאנד, סלואס וקוליוטה בבסיסט ג'יימס מקדונו והאחים גלן ושון דרובר על הגיטרה והתופים. במהלך השנתיים העוקבות חברי הלהקה יצאו לסיבובי הופעות ברחבי העולם ולאחר מכן לסיבוב הופעות שנקרא בשם Gigantour, שהתמקד בארצות הברית וקנדה והשתתפו בו להקות נוספות. מאסטיין יזם את הפסטיבל על מנת לעודד הופעות מטאל ואת פעילותן של להקות אחרות. סיבוב ההופעות הגיע לממדים כאלו שהוא הצטייר כאירוע המתחרה ב"Ozzfest", אותו ארגן אוזי אוסבורן. בהופעה בארגנטינה, מאסטיין הפתיע את הקהל והודיע שמגאדת' תמשיך לפעול ותוציא אלבום נוסף.
במהלך התקופה שלאחר הוצאת "The System Has Failed", מגאדת' בהרכבה החדש הגבירה את פעילותה: מאסטיין עבר להשתמש בגיטרות של חברת "Dean" ובעקבותיו גם עבר גלן דרובר. ב-21 במרץ 2006 יצא מארז האוסף "Arsenal of Megadeth" ב-DVD, וב-15 במאי 2006 מגאדת' חתמה עם חברת הפקות המטאל הידועה Roadrunner Records. ב-10 בפברואר 2006 הבסיסט ג'יימס מקדונו הוחלף בג'יימס לומנזו וב-15 במרץ, הקמע המצויר של מגאדת' "Vic Rattlehead" עוצב מחדש בתחרות מעצבים גרפיים באתר DeviantArt.com. ב-22 באוגוסט וב-5 בספטמבר הלהקה הוציאה אלבום הופעה כפול ו-DVD של סיבוב ההופעות Gigantour משנת 2005. ב-2 בדצמבר יצא אלבום ההופעה "" שצולם בהופעה בבואנוס איירס, ארגנטינה.
לאחר גיבושם של שירים חדשים, ב-19 באפריל 2006 חברי הלהקה החלו להקליט באנגליה את אלבומם האחד עשר. במספר קטעי תיפוף שהוקלטו, שון דרובר השתמש בציוד של ג'ון בונהאם מלד זפלין. לאחר הפסקה לסיבוב ההופעות Gigantour 2006, הלהקה חזרה ב-21 בנובמבר להקלטת האלבום בקליפורניה. ב-4 במרץ 2007 שוחררה רשימת השירים שתופיע באלבום. לבסוף, ב-15 במאי 2007 יצא לאור האלבום החדש של מגאדת', "United Abominations", כשעל עטיפתו ניתן לראות את ויק בגרסתו החדשה על רקע בניין האו"ם המותקף (שהופיע גם על עטיפתו של Peace Sells...But Who's Buying?). האלבום כלל 11 שירים, שחלקם הושמעו מוקדם יותר בהופעות חיות, ברדיו או ניתנו לשמיעה או הורדה מאתר הלהקה. האלבום עוסק כקודמיו בנושאים פוליטיים שונים (United Abominations, שם האלבום, הוא עיוות של United Nations) ומסתמן כאחד המוצלחים ביותר של מגאדת', שהגיע למקום השמיני ברשימת הבילבורד האמריקני.
ב-9 באוקטובר 2007 הוציאה הלהקה מארז מיוחד הנקרא Warchest ("תיבת מלחמה"). על עטיפת המארז צויר איור ממוחשב של שרשיר כדורי רובה, אשר מובלט החוצה מהמארז. המארז מכיל חמישה דיסקים: שלושת הראשונים מכילים שירים ודמואים אותם הקליטה הלהקה בין השנים 1985 ל-2004, הרביעי מכיל הקלטה של הופעה חיה שנערכה ב-1990 באנגליה והחמישי הוא DVD של הופעה שהוקלטה ב-1992 באולם ההאמרסמית' אפולו שבלונדון.
ב-15 בספטמבר 2009 יצא אלבומם הבא של הלהקה, "Endgame", הפעם עם כריס ברודריק כגיטריסט מוביל. האלבום הגיע למקום התשיעי ברשימת הבילבורד 200, למקום הראשון ברשימת אלבומי ההארד רוק ולמקום שני ברשימת אלבומי הרוק. הוא קיבל ביקורות טובות ונחשב לממשיך את הצלחתו של האלבום הקודם. יש שהשוו את האלבום עם אלבום מוקדם של הלהקה, "So Far, So Good... So What!".
העשור השני של המאה ה-21.
בפברואר 2010 חזר ללהקה הבאסיסט לשעבר של מגאדת', דייוויד אלפסון, וזאת ביוזמתו של המתופף שון דרובר.
ב-16 באפריל 2011 הלהקה הופיעה בישראל בפעם רביעית בתולדותיה. בהופעה שנערכה בגני התערוכה צפו כ-6,000 איש. בסוף ההופעה מאסטיין אמר שהם רוצים לחזור פעם נוספת לישראל.
אלבום האולפן ה-13 של הלהקה, TH1RT3EN, שוחרר ב-1 בנובמבר 2011. זה האלבום הראשון מאז איחוד הלהקה ב-2004, שבו משתתף הבסיסט דייוויד אלפסון.
השירים Sudden Death ו-Public Enemy No.1 מהאלבום TH1RT3EN בנוסף לשיר Head Crusher מהאלבום Endgame היו מועמדים לפרס גראמי בתואר ביצוע המטאל הטוב ביותר.
ב-2011 הלהקה הוציאה גרסה מחודשת לאלבום Peace Sells... But Who's Buying?, לכבוד חגיגות ה-25 שנים לצאתו לראשונה.
מגאדת' הודיעה על חידוש סיבוב ההופעות GiGantour בשנת 2012. סיבוב ההופעות יכלול את מגאדת', להקת ההבי מטאל הבריטית מוטורהד, להקת המטאל גותי האיטלקית לקונה קויל ולהקת ההבי מטאל הדנית VolBeat. בקיץ 2012 הלהקה יצאה לסיבוב הופעות עם הבדרן רוב זומבי.
לאחר כעשור בו ניגן דרובר בלהקה, הוא הודיע על עזיבתו בשל רצונו לנסות אפיקים חדשים. עד מהרה עזב גם ברודריק, בשל חילוקי דעות אומנותיים (ושניהם אגב הצטרפו ללהקת Act of Defiance). ב-29 במרץ 2015 נודע כי המתופף כריס אדלר מלהקת Lamb of God יעבוד עם מגאדת' על אלבומה החדש של הלהקה, ה-15 במספר. ב-2 באפריל נודע כי הגיטריסט הברזילאי קיקו לוריילו, לשעבר מלהקת אנגרה, הצטרף באופן רשמי ללהקה.
בשנת 2021 בעיצומי העבודה על אלבום החדש, פוטר דייוויד אלפסון מהלהקה עקב שערורייה מינית. את מקומו של אלפסון החליף באסיסט הלהקה לשעבר ג'יימס לומנזו שהצטרף לסיבוב הופעות, ולאחר כשנה במאי 2022, הודיעה הלהקה באופן רשמי כי ג'יימס לומנזו יצטרף באופן קבוע.
"ארבע גדולות הת'ראש" - סיבוב ההופעות.
בספטמבר 2009 הודיע לארס אולריך מלהקת מטאליקה כי הוא מתכוון לאגד את ארבע להקות הת'ראש הגדולות - מטאליקה, מגאדת', סלייר ואנתרקס - ולצאת לסיבוב הופעות. סדרת הופעות אלו, שבעה במספר, החלה ב-16 ביוני 2010 בוורשה, פולין והסתיימה ב-27 ביוני 2010 באיסטנבול, טורקיה. ההופעה שהתקיימה בסופיה, בולגריה ב-22 ביוני הועברה בשידור חי דרך לוויין לכ-450 תיאטראות ברחבי ארצות הברית ולמעל 350 ברחבי אירופה, קנדה ואמריקה הצפונית.
סגנון הלהקה.
מגאדת' היא להקה מגוונת מבחינת סגנונה המוזיקלי. היא אמנם נחשבת ללהקת ת'ראש, אך יחד עם זאת במוזיקה שלה ניכרת השפעה חזקה של הארד רוק והבי מטאל מחד ופאנק ורוק מלודי מאידך. סגנון הנגינה של מגאדת' קיבל מספר תפניות במהלך עשרים שנות פעילותה והושפע מגורמים שונים: הן מהנגנים שהיו חברים בלהקה בתקופות השונות ומהמוזיקה של הלהקות להן האזינו, הן מפעילותן של הלהקות המתחרות ובראשן מטאליקה והן מחברות התקליטים איתן עבדה הלהקה.
חברי הלהקה בראשית דרכה, בדומה למאסטיין, יצאו נגד התרבות השולטת בשנות השמונים ששמה דגש רב על ההופעה של האמנים ופחות על היצירה והמוזיקה (גלאם מטאל). עם פרישתו של מאסטיין ממטאליקה הוא הגדיר את הסגנון שהוא מועיד ללהקה שיקים בהמשך - נגינה מהירה עוד יותר בגיטרות וסגנון אגרסיבי, בהשוואה לסגנון הנגינה של מטאליקה.
באלבומים הראשונים של הלהקה, עיקר המכשול שעמד בפניהם היה השימוש בסמים ואלכוהול. התקציב של האלבום הראשון שימש ברובו לקניית סמים, כך שהאלבום סבל מפגמים טכניים. אלבומם המצליח ביותר מבחינה מוזיקלית וטכנית של הלהקה היה הרביעי, "Rust in Peace", שהיה לאלבום הראשון של ההרכב היציב ביותר של מגאדת'. מרטי פרידמן הביא למגאדת' השפעות מלודיות, שינוי מוזיקלי שהביא את הלהקה לכיוון אחר, אותו מרבית ממעריצי הלהקה לא אהבו. באלבום שהגיע אחריו, "Countdown to Extinction", ניכרה השפעה ראשונה של חברות התקליטים, משום שהיו בו פחות סולואים והיה פחות כבד מקודמו, אם כי האלבום זכה להצלחה מסחרית. באלבומם הבא, "Youthanasia", ניכרה השפעה בולטת יותר של חברות התקליטים. הסגנון באלבום זה היה איטי יותר ופחות מורכב מקודמיו. האלבום שהיווה נקודת שפל ללהקה היה "Risk", שבו הייתה התרחקות בולטת מאוד מהמטאל וניכרו בו השפעות מלהקות אחרות.