Purgatory was formed by Hendrie (bass/vocals), Lutfie (guitar), AL (Drums), and Arief (guitars) as a death metal band. In the beginning they formed this band without any serious meanings. There is no exact date of their formation, but certainly they had been around since 1991. They used to always sang the songs of Obituary and Sepultura. The name purgatory itself was inspired from a horror movie namely A Nightmare on Elm Street. There was a scene in the movie that displays the arrow that bear the word 'PURGATORY'. This later inspired L.T.F. and his little brother Al to use the name 'PURGATORY' as the name of their band.
The band released their first release, Abyss Call in 1995. The EP was later followed with the release of a compilation album by Rotocorp Records, namely Metalik Klinik I, wherein Purgatory contributed their song "Sakaratul Maut". A year later, under the label Rotocorp Records, the band released their first album, Ambang Kepunahan.
Travel to work in this band makes the personnel felt limited grip genre of music. Fresh ideas began to emerge clashed with a band that had been locked status of the genre. By the year of 2002, the band added a deejay and one more vocalist. This marking their change in music. The band also decided to wore masks. Purgatory released their second studio album 7:172 in 2003. This album marked the departure of Purgatory from death metal music in favor of nu metal music. 7:172 also had brought Purgatory to the fame. The echo of the album bounced wider than the band had expected. In this album, Eet Sjahranie, the guitarist of Edane, appears as a guest star as the additional rhythm guitarist on the first track off the album, namely "Paranoia". Following with the release of 7:172, Purgatory began to participate in some compilation albums. By the year of 2004, Morbid Noise Records put "Dragdown" (the fifth track off the album) on their compilation album namely Metaloblast. By the year of 2005, Purgatory contributed the song "Inside You" for OST. Gerbang 13 (Gate 13). The song also, in the same year, available on Sony BMG compilation album Revolution of Sound. In the same year, "M.O.G.S.A.W." (which stands for Messenger of God Sallallaahu Alayhi Wasallam, which refers to Muhammad) - the third track off the album 7:172 - was available on Sony BMG compilation album Planet Rock. In 2006, Purgatory
released their third studio album Beauty Lies Beneath. In the same year was chosen to represent Indonesia in The Art of Metal, a compilation album that is the project of Century Media (Germany) and Alfa Record (Indonesia), aligned with the world’s most powerful names, as : Napalm Death, Lacuna Coil, God Forbid, Shadows Fall and others. The song that Purgatory contributed in the album was "Downfall (The Battle of Uhud)".
The band had faced the name problems with the other bands from the other countries that bear the same name. There was a foreign lawyer commented ask the band to change its name, it is said that they had used this name earlier in the year 1999. Where at the time, YouTube does not exist yet.