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, and the band was 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 were 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.
The original LP, cassette and CD versions were released on 3 September 1990. The album was certified Gold by RIAA in January 1991. A re-mastered CD was released in May 2001. The album received a Grammy nomination for Best Metal Performance at the 20 February 1991 33rd Annual Grammy Awards.
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, as well as 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 left. 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.