The band was formed by Count Mortem in October 1999 who decided to call upon four members to get together because of their desire to play black metal. Rehearsals began immediately and the band rapidly began writing material, in which various influences which the band hadn't counted .. began seeping in, rapidly transforming their material into highly intelligent and creative music.
The first live show was thereby played a year from the formation of the band, exposing them to a considerable audience who at once appreciated this highly original form of extreme black metal. Recording for the first album soon started at Temple Studios in Malta. This album has a very high-quality recording and a professional production. In November 2001 the debut CD 'Withering in Voluptuous Embrace' was unleashed. The release consisted of highly dense and multilayered symphonic black metal, moving from delicate, morbid ambiences to vitriolic, violent atmospheres. In early 2002 the band released 500 original copies by themselves. After sending copies to different labels the band received very good responses. After taking many considerations Martyrium decided to sign with the Mexican label American Line Productions. The label decided to re-release their first album in the same year. This album is still in demand around the globe.
In the autumn of 2004, the band toured for the first time. The tour started in Belgium and then in the Northern part of France playing critically acclaimed shows with Morrigu and Earaction, Der Kaiser Der Narren, Kryzees and Positiv Hate respectively. There the band was welcomed with enthusiasm by the foreign metal heads. Five months later Martyrium together with Slit supported the Greek legends - Rotting Christ - at their gig in Malta which was very successful. By summer end of the year 2005 the band experienced another tour in central Europe where the band were also welcomed with even more enthusiasim than the previous year, celebrating a great launch for the second studio album.The second assault by the band, entitled 'The Carnage Lit By Darkness', continues to explore the stylistic alleyways heralded by their debut album, however, as can always be expected, a more progressive and deft instrumental touch makes its presence obvious from the start. This time the Martyrium Legion invaded Germany, France, Switzerland and Italy and were headliners for several gigs and played with bands such as Cruachan, Eluveitie, Black Messiah, Barritus, Ivenberg and German Veterans Daargesin.
In The First quarter of 2006, Martyrium supported German Death Metal Band – PURGATORY during their tour. 2006 also saw Martyrium in a yet another change of style. This time focusing more on heavy guitar work and creating more dark atmospheres to the songs, and tracks like Awakening The Ancient, and Into The Labyrinths Of The Absu went down really well with the band’s fans.
In November 2010, the band released their 3rd blasphemy entitled "Awakening the Ancient" under the label American Line Productions/Witchcraft Records, and immediately got really good reviews from distributors and other metal web-zines. The CD is expected to be launched officialy in Malta too in mid-2011.