In 1989, Judas Priest had just come off of two of their less successful albums with Turbo, and Ram It Down, both of which attempted to incorporate synthesizers and glam rock elements. The band was then widely dismissed as passe and unable to compete with the younger generation of metal groups such as Metallica, Megadeth, Anthrax, and Slayer. In response, Priest adopted a more contemporary speed metal sound on Painkiller. The effort paid off—and the album became one of their most successful efforts—its songs becoming staples of their live setlist. Rob Halford claimed in an interview that the song "Hell Patrol" is about US Air Force pilots flying missions in the Gulf War which started a few months before the release of the album.
Despite the album being finished in March 1990, the album's release was delayed due to the pending, much-publicized subliminal message trial that began on 16 July 1990. The band was the subject of a civil lawsuit alleging their recording was responsible for the suicide attempts of two young men in Reno, Nevada on 23 December 1985. The case was eventually dismissed on 24 August 1990. With the trial behind them, the band finally released the album on 3 September 1990 on LP, cassette and CD.
Following the tour for this album, singer Rob Halford left the band in May 1992 and maintained little contact with his former bandmates throughout the 1990s. The reason for this was growing tensions within the band, along with Halford's desire to explore new musical territory by creating a new band of his own, Fight, which forced him to legally leave Judas Priest to allow this creation to be sold. Judas Priest remained inactive for several years after Halford had gone; however, the band would eventually re-vamp, record, and tour, recruiting new singer Tim 'Ripper' Owens in 1996, who would perform on the studio albums Jugulator and Demolition.