Dopo la separazione dai Seelenkrank, il cantante Chris Pohl lasciò trascorrere un po’ di tempo prima di riproporre un progetto musicale molto simile ma con una nuova casa discografica ed un nuovo nome: Blutengel. I testi dei loro brani sono scritti principalmente in tedesco e in inglese e all’interno dei brani si affiancano voci maschili e femminili che cantano su una base sonora di tipo elettronico. Affrontano tematiche che spaziano su tutti gli aspetti dell’amore, da tragici e romantici amori senza speranza, agli aspetti più carnali del desiderio sessuale, a cui uniscono un look ispirato a suggestioni di tipo vampirico.
Le parti vocali femminili erano originariamente affidate a Kati Roloff e Nina Bendigkeit, che cantarono nel primo album del gruppo, Child of Glass, pubblicato nel 1999. Nonostante il discreto successo riscosso da questo primo lavoro, il gruppo non diede più segnali di sèper i due anni successivi, che dedicarono alla realizzazione dell’album successivo, Seelenschmerz.
Nel frattempo la formazione della band era cambiata: nel 2000 Nina Bendigkeit, fino ad allora la voce principale, riuscì ad affermarsi come fotografa professionista e lasciò il gruppo, venendo quindi sostituita da Kati Roloff come prima voce femminile, mentre come seconda voce fu ingaggiata Gini Martin. Brani come “Children of the Night”, “Der Spiegel”, “Soul of Ice” resero Seelenschmerz un album di successo, che mancò di poco l’ingresso nella classifica dei 100 album più venduti in Germania. Il gruppo inoltre si esibì per la prima volta dal vivo al Wave Gotik Treffen di Lipsia.
Alla fine del 2001 hanno pubblicato il singolo Black Roses, con Constance Rudert come cantante che ha anche affiancato il gruppo in un’esibizione dal vivo al Dark Storm Festival: si trattò dell’ultima volta in cui il gruppo si è presentato al pubblico con la sua formazione originale poichè Kati e Gini poco dopo abbandonarono per motivi personali, fondando un proprio progetto musicale, Tristesse de la Lune. Le due sono state quindi sostituite appunto dalla Rudert e da Eva Pölzing.
Con la nuova formazione, il successivo album del gruppo, Angel Dust si piazzò al 58° posto della classifica tedesca alla prima settimana e successi come “Angel of the Night” e “Vampire Romance” contribuirono ad aumentare la loro popolarità.
Nel 2004 hanno pubblicato il loro quarto album, Demon Kiss, seguito dal DVD Live Lines nel 2005. Nell’ottobre dello stesso anno però anche Eva Pölzing decise di lasciare per dedicarsi a stusi e progetti personali, venendo sostituita da Ulrike Goldmann (ex-Say-Y) prima della pubblicazione degli EP The Oxidising Angel e My Saviour