Los dos Dave´s se encontraban en su peor momento pero sin embargo se las ingeniaban para seguir dando batalla, el siguiente problema con el que se encontraron fue casualmente el cambio de integrantes, el primero en ser despedido fue Jeff Young que igualmente ya estaba podrido de los malos tratos, este volvio a formar su anterior banda "Broken Silence" sin ningun exito.
El otro que fue despedido fue Chuck Behler lo que dejo a Megadeth reducido a su esencia Ellefson / Mustaine.
La ultima aparición con la formación de So Far... fue en la pelicula "The Decline Of Western Civilization II: The metal years" en la cual se mostraba a los musicos de la escena metalica de los Angeles como unos idiotas sin nada que decir. Raramente el unico que se salvaba era Mustaine que pese a lo dado vuelta que estaba (bastaba con mirarle la cara) hizo unas declaraciones de lo mas interesantes. Eso si, a Metallica lo defenestro.

Al primero que tomaron fue a Nick Menza (como ya le habia avisado Mustaine), pero no fue su ingreso oficial hasta Junio del 89' casi 7 meses despues.
En medio de tantos cambios se las arreglaron para largar un nuevo simple que seria parte del soundtrack de la pelicula "Shocker", el tema elegido fue "No More Mr. Nice Guy", de Alice Cooper.
El productor del simple fue Desmond Child. El saldo fue positivo pero la relación entre las partes fue desastrosa. El tema fue muy popular y estuvo en el puesto numero 13 de la revista Billboard.
Esto ayudo a mantener a la banda mas o menos popular en estos tiempos de cambio. Este fue el unico tema que grabo Megadeth como trio: Mustaine/Ellefson/Menza.
Luego las cosas se empezaron a poner mejores, tanto Mustaine como Ellefson empezaron a mejorar su situación y solo les quedaba encontrar a un gran guitarrista. La tarea llevo casi una año, pero finalmente en Febrero del '90 el puesto quedo en manos del virtuoso Marty Friedman (ex-Cacophony) que figuraba en el catalogo de Shrapnel Records.
Segun palabras de Mustaine "es ironico que durante todo el tiempo donde estuvimos buscando guitarrista, la foto de Marty siempre estuvo en el escritorio de nuestro manager (Ron Lafitte). Pudimos haberlo audicionado hace mucho pero nos equivocamos en prejuzgarlo por su imagen en vez de por su talento".
Dicen las malas lenguas que uno de los tantos guitarristas audicionados fue nada mas y nada menos que Diamond Darrel de Pantera, pero no los convencio (¿?).

Ahora ya con Megadeth totalmente reestructurado, era tiempo de entrar nuevamente al estudio y las cosas pasaron rapido puesto que en ese mismo año (1990) Rust In Peace salio a la calle. El disco era absolutamente impresionante y era sin ningun lugar a dudas el mejor trabajo de Megadeth hasta ese momento. Las letras tocaban temas como las guerras, el gobierno, etc...
Otra cosa que se destacaba del album era el trabajo asombroso de Marty y Dave en guitarras.
El primer simple salio el 24 de Septiembre y era del tema Holy Wars, raramente esta canción alcanzo solo al puesto 24 de la Billboard, pero bueno, no estaba tan mal. Igualmente el disco no anduvo nada mal dado que llego al puesto 8 de la Billboard, (para una banda de heavy Metal esta muy bien).

El otro video que hicieron fue el de Hangar 18 (un video barbaro), raramente esta canción (que ya es un clasico para todos los fans de Megadeth) solo llego al puesto 26.
Luego Megadeth se embarco en una gira que seria de las mas resonantes de todos tiempos, el "Clash Of Titans". En Europa el cartel se formaria con Slayer, Megadeth, Testament y Suicidal Tendencies. Algo llamativo es que Slayer cerraba todas las actuaciones, esto era debido a que el manager de ellos fue el principal responsable de que el festival se lleve a cabo.
Igualmente (algo raro) Dave se mostro muy medido al respecto en sus declaraciones y solo dijo que "pienso que nosotros merecemos el cierre pero yo no soy ni promotor ni nada de eso".

Al año siguiente (1991) la cosa se iba a poner aun mejor puesto que en la gira por EE.UU. al cartel se le sumaria Anthrax quedando el cartel conformado por: Megadeth, Slayer, Anthrax y (en ese momento los desconocidos) Alice In Chains. En EE.UU. las cosas serian un poco mas democraticas puesto que cerrarian los conciertos una noche cada uno.
Luego Megadeth fue invitado a participar del mega-festival de rock mas grande de la historia, el Rock In Rio, alli tambien tocaron (entre otros) Guns N' Roses, Faith No More, Judas Priest, Queensrÿche y Sepultura.

Megadeth tambien estuvo invitado al decimo aniversario de la revista KERRANG! celebrado en Londres.
El tour que le siguio fue el "Oxidation Of The Nations Tour" en el que Megadeth conto como soportes a Alice in Chains y The Almighty.
Luego salio a la venta el video "Rusted Pieces" en el cual se encontraban todos los videos de Megadeth hasta el momento excepto el de No More Mr. Nice Guy.
Tambien como un elemento promocional largaron a la venta el "Maximum Megadeth" que incluia lo mejor de Megadeth hasta el momento.

Lo bueno en este momento es que Megadeth no tuvo cambios en la formación, seguian los mismos cuatro lo cual parecia casi imposible...

Si, evidentemente las cosas estaban cambiando...