During the spring of 2000, drummer Håkan Björklund and guitarist Mattias Edin were working on ideas in a scuffed rehearsal place in Kramfors, Sweden. Eventually they would be joined by vocalist Fredric "Rengulfed" Edin and guitarist Lars Engström.
Under the name of Marchosias the band recorded its first demo at the Underground Studios, Västerås, a demo that would be released in January 2002. It would nevertheless receive little response other than some praise from a few companies.
In the spring of 2002, bass player Andreas Edin and keyboard player Dennis Bobzien would team up to develop the music further. Simultaneously guitarist Lars Engström left the band due to musical differences. His replacement was Henrik "Keso Heiko" Johansson. A change that was - as they say - for the better.
With the new members highly active in developing the music further, soon the band found itself ready for a second demo. Once again the band would travel to Västerås and Pelle "Da Rose" Rosén in order to record what would result in the band's second demo. As a result of this second demo, in early spring 2003, Black Mark came with an offer the band could not resist.
From having been a quartet initially, in 2003 the band went on to become a six-piece act with higher ambitions, and had now settled on a final name for the band.
In the summer of 2003, the band completed its debut album entitled "Cell666" at Studio Underground in Västerås.