Following the positive reception Slayer's previous release Hell Awaits had received, the band's producer and manager Brian Slagel realized the band were in a position to hit the "big time" with their next album. Slagel negotiated with several record labels, among them Rick Rubin and Russell Simmons's Def Jam Recordings. However, Slagel was reluctant to have the band signed to what was at the time primarily a hip hop label. Slayer drummer Dave Lombardo was made aware of Rubin's interest, and initiated contact with the producer. However, Slayer's remaining members were apprehensive at leaving Metal Blade Records, with which they were already under contract.
Lombardo contacted Columbia Records, which was Def Jam's distributor, and managed to get in touch with Rubin, who along with photographer Glen E. Friedman agreed to attend one of the band's concerts. Friedman had produced Suicidal Tendencies's self-titled debut album, in which Slayer vocalist Tom Araya made a guest appearance in the music video for the album's single "Institutionalized", pushing Suicidal Tendencies's vocalist Mike Muir. Around this time, Rubin asked Friedman if he knew Slayer.
Guitarist Jeff Hanneman was surprised by Rubin's interest in the band, and was impressed by his work with the hip hop acts Run DMC and LL Cool J. During a visit by Slagel to a European music convention, Rubin spoke with the band directly, and persuaded them to sign with Def Jam. Slagel paid a personal tribute to Rubin, and said that Rubin was the most passionate of all the label representatives the band were in negotiations with. Following the agreement, Friedman brought the band members to Seattle for two days of publicity shots, possible record shots, and photos for a tour book; Rubin felt no good photos of the band had been taken before that point. One of the photos was used on the back cover of the band's 1988 release South of Heaven.