Fairyland a été créé en 1998 par Willdric Lievin et Philippe Giordana, rejoints dès les premières semaines par Thomas Cesario. Le groupe s'appelait alors Fantasia. Partageant la même passion pour le metal symphonique, les trois membres ont commencé à travailler sur les premiers morceaux du projet. En 1999 sort la première démo, Tribute To Universe. Le style du groupe a ensuite évolué en ajoutant une importante touche de fantastique donnant un caractère épique à leurs compositions. La deuxième démo, Realm Of Wonders, sort en 2002. Elle a bénéficié de bonnes critiques dans le milieu du metal. Fairyland rencontre alors plusieurs musiciens, dont le guitariste Anthony Parker qui jouait alors dans le groupe français Heavenly. Of Wars In Osyrhia est enregistré au Wizard Studio de février à novembre 2002.