Le groupe a été fondé en janvier 1999 par les frères Gabriel Holland (bass) et Fernando Holland (drums), et leur ami Renato Plata. Ils avaient surtout comme influence Blind Guardian et Iron Maiden. En avril de la même année, les frères Holland ont rencontré le guitariste Victor Montalvão et il a joint le groupe par la suite qui se nommait à ce moment-là, Heaven's Fall. Ils vont la composition les mois qui ont suivi, sans chanteur, mais ils ont fini par se séparer. Gabriel et Victor ont tenté de garder le groupe en vie, mais sans succès.





En 1999, le groupe revient avec le nom Heaven Falls et le chanteur Márcio Mitzael et le clavieriste Rodrigo Evora, qui est un ami du guitariste Renato Plata. En janvier 2000, ils veulent tenter quelque chose et ils décident d'avoir deux chanteurs. La chanteuse Sabrina Carrión joint le groupe. Elle participait déjà à un projet de Victor. La formation reste intact jusqu'en mai 2000, lorsque Renato, Rodrigo, Márcio et Fernando quittent le groupe pour diverses raisons. Philip Martins (guitare), Werther Azevedo (clavier), Hugo Navia (chanteur) et Fabio Rogers (drums) joignent tous le groupe.





Ils font leur premier en décembre 2000 au Night Rock de Rio De Janeiro. Après le spectacle, Hugo et Philip quittent le groupe. Ils ont de la difficulté cette fois à trouver des nouveaux musiciens et ils ont décidé qu'il y aurait seulement Sabrina comem chanteuse. En juin, Gabriel quitte le groupe à son tour et il est remplacé par Daniel White. Par la suite, Werther quitte le groupe. Sabrina, Victor, Fabio et Daniel ont fait quatre spectacles ensemble. Werther a fait deux des spectacles comme musicien invité. Ils décident d'enregistrer un demo, Winter's Dance, qui contiendra 4 chansons. Ils font l'enregistrement de décembre 2001 à mars 2002 au Fast Foward Studio avec l'aide de l'ingénieur du son Maurício Meloni. Menezes Bernardo, qui avait été le clavieriste pour l'enregistrement du demo, a suivi le groupe jusqu'en juin 2002. Durant la même période, ils ont ajouté le guitariste Sidney Júnior à la formation, mais il a quitté lui aussi en juin 2002. Ils ont signé avec la compagnie Hellion Records. En septembre 2002, le guitariste Davis Vasconcellos joint le groupe. Ils sont retournés dans le même studio que pour l'enregistrement du demo pour l'album Ethereal Dreams. À ce moment, la formation avait comme membre Sabrina Carrión (chanteuse), Victor Montalvão (guitare), Vasconcellos Davis (guitare), Daniel White (bass) et Fabio Rogers (drums). Leur premier album contient neuf chansons, At The Gates, Castles of Illusion, Suffering Symphony, Damned Queen, Inside My Mind, Temple of Lies, Winter's Dance, Inner Prison and And the Heaven Falls... et il est sorti en 2003.