2, alem de ser divulgada em varias coletaneas de fanzines e distribuidoras do pais e do exterior. Gravadoras como Dark Realm (USA), Uncle Underground (Belgium) e artistas como Vincent (Sadistic Intent-USA), Jeff Gruslin (ex-Vital Remains/USA), Christopher Szpajdel (Promotor de show na Europa e Artista grafico de bandas norueguesas como Emperor, Old Mans Child, Satyricon, Immortal e outros) citam a banda em varias entrevistas como uma nova promessa para o metal sul-americano.Com a saida de Ricardo Oitaven e Valdo Jr. a banda se desestabiliza, ficando apenas Danilo e Vlad no grupo.No ano de 1996, apos alguns testes frustrados com alguns musicos, uma nova formacao completa e apresentada com a volta de Alexandre Deminco ao seu posto, trazendo consigo o baixista Roberto Souza, o guitarrista Jafet Amoedo e a tecladista Elaine.Apos um hiato de 3 anos sem se apresentar ao vivo, finalmente os palcos puderam ver novamente o grupo na ativa.Elaine se muda para a Noruega, sendo rapidamente substituida pelos tecladistas Luciano Veiga e Ovidio Amoedo.1997: O MALEFACTOR lanca uma musica nova "Under The Law of the Sword na coletanea DoisDaBahia, com 9 bandas de metal baianas, sendo uma previa do primeiro album.Celebrate Thy War1999: Apos 8 anos de intensa contribuicao para com o underground, eis que chegara a hora do debut album. Celebrate Thy War e lancado pelo selo paulista Megahard Records, alcancando otimas notas na midia e fazendo com o que o MALEFACTOR leve 2500 pessoas a Concha Acustica de Salvador no lancamento do album, sendo ate hoje um dos maiores publicos num show nao gratuito de metal na cidade.Foram quase 2 anos tocando pelo Nordeste, mas sempre encontrando dificuldades para ir a outras regioes do pais e para fora dele.The Darkest ThroneEm 2001, Jafet e substituido por Martin Mendonca (Pitty) e gravam o album The Darkest Throne, sendo que Jafet gravou metade das musicas.Pensando em conquistar outros mercados o grupo parte para uma tour de 30 dias pela Europa, levando Wallace Guerra na segunda guitarra e Marcelo Antunes como session member, pois Roberto teve inumeros problemas na epoca, nao podendo ir na tour.Os shows foram muito bons no geral, conseguindo colocar o nome do grupo na imprensa europeia e recebendo elogios de zines e revistas metalicas do velho mundo. A revista portuguesa LOUD! Comentou o show do Malefactor em Lisboa como um dos melhores eventos daquele ano no pais.Na Belgica o Malefactor sem apresentou no Marching Evil Festival, ao lado de bandas da Belgica (Iconoclasm), Franca (Sword e Arkhon Infaustus), e Inglaterra (Adorior e Throne of Nails). Na Alemanha o Malefactor fez uma mini-tour ao lado das bandas Pandemia e Fleshless, ambas da Republica Tcheka, aonde vendeu todo o seu merchandise e conquistou um grande numero de apreciadores.Na volta, Wallace foi substituido por Ricardo Sanct (atual Veuliah) e a The darkest tour passou por 12 estados do pais, 3 paises (Alemanha, Portugal e Belgica), colocando a banda entre as mais representativas bandas do metal brasileiro.A tour ainda contou com a banda abrindo shows de bandas como Angra, Destruction (Alemanha), Kreator (Alemanha) e Monstrosity (Estados Unidos).BarbarianPara 2003 o grupo deu mais uma