During their world tour in support of So Far, So Good... in February 1988, Mustaine noticed problems developing with Behler. Six months later, Mustaine fired both Behler and Young. In July 1989, Nick Menza was hired to replace Behler on the drums. After a lengthy search for a new lead guitarist, Megadeth enlisted Marty Friedman, who officially joined in February 1990. The lineup remained unchanged for almost eight years, until Menza discovered a tumor on his knee, which forced him to leave the tour to undergo surgery. He was replaced by Jimmy DeGrasso, temporarily at first. Following the Ozzfest tour in 1998, however, DeGrasso replaced Menza permanently, after Mustaine claimed that Menza had "lied about having cancer". Following the release of Risk, the band began a new world tour in September 1999. Three months into the tour, Friedman announced that he would be leaving the band, citing "musical differences". Megadeth enlisted guitarist Al Pitrelli as Friedman's replacement in January 2000. In early 2002, Mustaine suffered several injuries, which led him to announce in a press release that Megadeth had disbanded. Following nearly a year of recovery, Mustaine began work on what was to be his first solo album. The new material was recorded with session musicians Vinnie Colaiuta and Jimmy Lee Sloas, but the project was put on hold when Mustaine agreed to remix and remaster Megadeth's eight-album back catalog with Capitol Records.
In May 2004, Mustaine returned to his newest recordings, intended as a solo effort, but because of outstanding contractual obligations with the band's European label EMI, he was forced to release one more album under the "Megadeth" name. Mustaine decided to reform the band, and contacted the Rust in Peace line-up to re-record backing tracks on his latest songs. While drummer Nick Menza initially signed on, Marty Friedman and David Ellefson were both unable to come to an agreement with Mustaine. Chris Poland was hired by Mustaine to contribute only with guitar solos to the new album. Megadeth began a world tour in October 2004, enlisting touring bassist James MacDonough, and guitarist Glen Drover. While in rehearsal for the tour, newly returned drummer Nick Menza once again parted ways with the band, as he was unable to prepare for the physical demands of a full U.S. tour. He was replaced five days before the first show by Shawn Drover, brother of new guitarist Glen Drover. In February 2006, MacDonough left the band, citing "personal differences" for his decision, and was replaced by bassist James LoMenzo. Two years later, Dave Mustaine announced that Glen Drover had quit Megadeth to focus on his family. He was replaced by Chris Broderick. On February 8, 2010, David Ellefson rejoined the band, replacing James LoMenzo.
In late November 2014, Shawn Drover quit the band after ten years, wanting to pursue his own musical interests. This was quickly followed by the departure of Chris Broderick, due to artistic and musical differences. Ellefson denied rumors that the band would disband, and said he and Mustaine would continue working on new music. In early 2015, Megadeth announced that Brazilian guitarist Kiko Loureiro was hired as the new guitar player for the band to record Megadeth's 15th studio album alongside Lamb of God's drummer, Chris Adler as a recording session member.