In November 2000, Megadeth signed with new label Sanctuary Records. The band returned to the studio in October to put the finishing touches on their next album, which had been near completion before the band joined the "Maximum Rock" tour six months earlier. Following the overwhelming negative response to Risk, Mustaine fired manager Bud Prager, and decided to self-produce Megadeth's next album. The World Needs a Hero, the first Megadeth album since Peace Sells... but Who's Buying? to be written entirely by Mustaine (with one contribution from Al Pitrelli on "Promises"), was released on May 15, 2001 to mixed reviews. While the album marked a return to form following the attempted mainstream rock direction featured on Risk, some critics felt the album fell short of expectations. Mustaine himself likened the album to be the first major turn of a huge ship at sea, trying to right itself and get back on course. The album's lead off single, "Moto Psycho", reached #22 on the Billboard Mainstream Rock charts, also receiving regular airplay on VH1's Rock Show.
Touring in support of The World Needs a Hero began in the summer of 2001 in Europe supporting AC/DC, followed by an American tour with Iced Earth and Endo in September. The tour was cut short however, following the attacks on America on September 11, the band were forced to cancel all scheduled dates, including a DVD shoot set in Argentina. Although they did perform one show at the Commador Ballroom in Vancouver, B.C. on September 12. Instead the band played two shows in Arizona in November, which were filmed and later released as Rude Awakening, Megadeth's first official live release. The DVD went gold on July 23, 2002. In February 2002, Mustaine remixed and remastered Megadeth's first album, Killing Is My Business... and Business Is Good!, with modern mixing and mastering techniques used on modern metal albums, and added bonus tracks.