El productor Fredrik Nordström tenía la ambición de crear una banda de power metal propia durante mucho tiempo, pero tuvo dificultades para encontrar a alguien con ideales musicales similares a los suyos. Sin embargo, mientras estaba de vacaciones en las islas griegas durante el año 1999, Nordström conoció al joven guitarrista Gus G (de Firewind ). Los músicos se llevaban bastante bien, a pesar de una diferencia de edad de más de una década. Comenzaron los planes para una banda: Gus ya había planeado mudarse a Gotemburgo , y cuando llegó, buscó a Fredrik en Studio Fredman para comenzar a escribir.
La primera persona a la que se pidió unirse a la nueva banda fue Snowy Shaw (de King Diamond , Mercyful Fate y Notre Dame ), pero el baterista inicialmente rechazó su invitación. Más tarde cambiaría de opinión y aceptó tocar en el álbum debut de la banda en una capacidad de sesión.
El vocalista Niklas Isfeldt había hecho coros para algunas de las canciones de HammerFall producidas por Nordström, y como no estaba involucrado en ningún proyecto importante en ese momento, aceptó tomar el puesto. También trajo consigo a su viejo amigo y compañero de banda de Pure-X Peter Stålfors , quien asumió las funciones de bajo.
Hasta el momento en que se tomaron las primeras fotos promocionales, toda la banda nunca había estado en el mismo lugar a la misma hora antes. Algunos miembros ni siquiera se conocían.
La banda pronto consiguió un trato con Century Media Records , y pretendía llamarse Dragonslayer debido a los temas medievales y fantásticos de las canciones escritas por Gus y Nordström. El sello no encontró el nombre lo suficientemente original, por lo que la banda se conformó con el nombre Dream Evil, inspirado en el álbum de Dio del mismo nombre.
El álbum debut de Dream Evil fue lanzado en abril de 2002 y recibió comentarios positivos de la prensa de metal. En un momento, el álbum, titulado Dragonslayer , alcanzó el número uno en las listas de importación japonesas . La banda procedió a tocar en una serie de festivales y también apoyó a Blind Guardian durante una parte de su gira mundial.