Background and production
In 1988, Megadeth appeared at the Monsters of Rock festival at Donington Park in the UK, alongside Iron Maiden, Kiss, Helloween, Guns N' Roses, and David Lee Roth. The band performed to an audience of more than 100,000 people  and was soon added to the "Monsters of Rock" European tour, but dropped out after the first show due to bassist David Ellefson's drug problems. Further issues within the band caused frontman and guitarist Dave Mustaine to fire drummer Chuck Behler and guitarist Jeff Young, and canceled their scheduled 1988 Australian tour. Nick Menza, previously Behler's drum tech, was hired as the band's new drummer. The search for a new guitarist was a drawn out process; Mustaine examined a number of guitarists for the job, including Dimebag Darrell of Pantera and Jeff Waters of Annihilator, and the former was initially offered the job before declining. According to Mustaine, one of the last guitarists he had heard about, Marty Friedman, had sent him a copy of Dragon's Kiss, on which Friedman played. Upon listening to the record, Mustaine had Friedman come in to audition and hired him. This would become the band's first stable line-up and, as recognized by fans, the 'classic' Megadeth lineup.
The title "Rust in Peace" was inspired by a bumper sticker that Mustaine saw on the back of a vehicle while driving home from Lake Elsinore, California. The sticker read: 'May all your nuclear weapons rust in peace'. Mustaine liked the concept and decided to use it as a title for Megadeth's upcoming album. Rust in Peace was recorded in Rumbo Studios with producer Mike Clink, while the mixing was handled by Max Norman. Clink was brought in for his work on both Guns N' Roses' Appetite for Destruction and UFO's Strangers in the Night. The producer's work dealt mostly with the bass, drums and Friedman's guitar. In a 2002 interview, Mustaine declared that they "really didn’t make the record with [Clink]" as at the time he was focused on Guns N' Roses' Use Your Illusion I and II — which were also being recorded at Rumbo — and stated most of the work in the album was done by himself, Norman, and engineer Micajah Ryan.
The album artwork was created by artist Ed Repka, who previously had done the cover for Peace Sells... but Who's Buying? in 1986. It references "Hangar 18", and depicts band mascot Vic Rattlehead and world leaders of the era viewing an alien body. The depicted world leaders, left to right, are British Prime Minister John Major (although the identity is disputed), Japanese Prime Minister Toshiki Kaifu, West German President (and later President of a reunified Germany) Richard von Weizsäcker, Soviet leader Mikhail Gorbachev, and U.S. President George H.W. Bush. In addition to creating the album's cover, Repka also supplied artwork for the album's two singles.