Messiah's debut album, Hymn to Abramelin, was released in 1986 through Chainsaw Murder Records. Their second LP, titled Extreme Cold Weather, came out in 1987 and was re-issued on CD three years later by Nuclear Blast. The release also contained the band's debut album. The band then managed to sign to a German major metal label, Noise Records, which released their next album, Choir of Horrors, in 1991. Messiah released two more albums, Rotten Perish and Underground, through Noise, but disbanded in the mid-1990s. Although the band members have since rehearsed together and gave a concert, they have decided not to re-unite.