Rust in Peace (1990–1991)
Durante el periodo de desintoxicación y sobriedad de Mustaine éste empieza a buscar sustituos de Young, dando al final con Marty Firedman en 1990 después de barajar nombres como Dimebag Darrell, Joe Holmes o Lee Altus. El guitarrista de Guns N' Roses, Slash, estuvo creando mezclas con Mustaine y Ellefeson y, parecía que estaba a punto de ser agregado a Megadeth, pero finalmente continuó con Guns N' Roses. Dimebag Darell Abbott, de Pantera también audicionó, y se le ofreció la oportunidad eventualmente. Darrell, sin embargo, no se uniría sin su hermano, el baterísta de Pantera Vinnie Paul Abbott. Habiendo contratado recientemente a Nick Menza, la banda se forzó a declinar la oferta a Darrell. In 1987, un Jeff Loomis de 16 años, de las bandas "Sanctuary" y "Nevermore", audicionó tiempo después de la salida de Chris Poland. Más tarde, Mustaine felicitó a Loomis por su habilidad en la guitarra, pero fue rechazado por su edad. Loomis más tarde vió a "Cacophony" con Marty Friedman y Jason Becker en una gira, y le contó a Friedman, quién apenas había lanzado su primer disco solista en 1988, acerca de la experiencia. Después, Friedman también audicionó por el lugar, pero fue inicialmente rechazado por Mustaien por tener el cabello pintado de varios colores. Sin embargo, siguiendo a lo que Mustaine llamó "Rock School 101", Friedman oficialmente se unió a Megadeth en Febrero de 1990.
Un Megadeth revitalizado entro a los Rumbo Studios en Marzo de 1990 con el co.productor Mike Clink para iniciar trabajando en lo que se convertiría en su álbum más aclamado por las críticas hasta la fecha, Rust In Peace. Por primera vez en su carrera, la banda permaneció sobria mientras trabajaban en el estudio, aliviando muchos problemas que habían tenido grabando en álbumes anteriores. Clink también fue el primer productor en producir satisfactoriamente un álbum de Megadeth desde el inicio hasta el final sin tener que ser despedido.
Lanzado mundialmente el 24 de Septiembre de 1990, Rust in Peace fue un éxito entre los fans y la crítica por igual, debutando como el número #23 en los Estados Unidos y #8 en Reino Unido. El estilo de escritura de Mustaine adoptó un tinte complejo progresivo, y el sonido mostro ser mucho más estricto, haciendo que Allmusic citará que "Rust In Peace es el álbum con mayor esfuerzo musical de Megadeth". El álbum incluyo los sencillos "Holy Wars... The Punishment Due" y "Hangar 18", además de que ambos tuvieron videos musicales y siguen siendo tocados en vivo hasta la fecha. Rust In Peace vendió mas de un millón de copias en los Estados Unidos y recibió nominaciones al Grammy en 1991 y 1992 por Mejor Interpretación de Metal.
Durante 1990, Megadeth se une a Slayer, Testament y Suicidal Tendencies en la gira europea Clash of thee Titans, así como a Judas Priest en su exitosa gira Painkiller, la cual acabó con una actuación en la segunda edición de Rock in Rio ante 120 000 personas. En 1991 se une a una gira por los Estados Unidos con Slayer, Anthrax y Alice in Chains. Esta gira estuvo a punto de cancelarse debido a los constantes enfrentamientos de Tom Araya y Dave Lombardo con Dave Mustaine, ya que Dave hizo a la prensa una serie de ataques verbales contra Tom Araya sobre todo tipo de cosas, desde sus hábitos en su tiempo libre hasta su mal olor corporal. Araya le devolvió el ataque con unos cuantos comentarios sobre las inseguridades personales de Dave Mustaine. Pero las peleas terminaron cuando llegaron para hacer un concierto en Phoenix, Arizona. Mustaine entró en los camerinos de Slayer con la mano tendida y pidiendo disculpas por las desagradables observaciones y la prensa negativa que esto había generado. Tras finalizar la gira, Megadeth compuso la canción "Go to Hell" para la banda sonora de la película Bill & Ted's Bogus Journey.
Megadeth junto con varios miembros de Slayer y Testament durante la gira Clash of the Titans que tuvieron en Europa.
