En 1998, firmaron un contrato con Dragonheart Records, con la cual publicaron su primer álbum, Romantic Tragedy's Crescendo.
El disco recibió una crítica positiva y llegó a vender 12.000 copias.
Durante este periodo, la banda contó con el apoyo de Amorphis en su gira italiana.
El álbum presenta un sonido más agresivo, sin perder el lado romántico del grupo.
Después de la publicación del álbum, realizan una gira por Italia y México.