C'est en 1986 qu'ils enregistrèrent leur premier démo, "Metricide". En 1988, Elegy partirent en tournée avec les groupes King Diamond et Angelwitch après avoir enregistré leur deuxième démo, "Better Than Bells". Malheureusement, le "line-up" du groupe changea avec l'arrivée de Ed Warby à la batterie et de Eduard Hovings au chant, avec eux ils enregistrèrent leur troisième démo, "The Elegant Solution". En 1993, le groupe remporta un concours de recherche de talents et ils gagnèrent l'enregistrement de leur premier album, Labyrinth Of Dreams", obtenant par la même occasion une entente avec la compagnie Shark Records.
En 1994, ils ont droit à un autre changement de "line-up" avec l'arrivée de Dirk Bruinenberg pour remplacer Ed Warby, et de Gilbert Pot à la guitare, ils enregistrèrent aussi leur deuxième album, "Supremacy", qui sortit au Printemps de cette même année. Ils ont même fait une tournée avec des groupes comme Annihilator, Phantom Blue, The Gathering et Gorefest. En 1995, leur troisième album, "Lost", vut le jour et fut publié en Été de cette même année. Il reçut d'excellentes critiques. Malheureusement, Eduard Hovinga et Gilbert quittèrent le groupe juste avant que la tournée avec Yngwie Malmsteen ne commence. En 1996, ils trouvent un nouveau chanteur, c'est-à-dire Ian Parry, ex-membre de Hammerhead, Mono Pacific et Airrance. Avec plus de 10 ans d'expérience, une très bonne carrière solo et une voix brillante qui fait plus de trois octaves, il fut le remplaçant parfait. Le groupe enregistra aussi le EP "Primal Instinct" qui fut publié en Été 1996.
En Mai 1997, l'album "State Of Mind" fut publié et Elegy supportèrent Stratovarius pendant une tournée européenne à très grand succès. En 1999, on eut droit à un autre changement de "line-up", mais rien de trop terrible puisque ce ne fut que l'arrivée de Chris Allister aux claviers. Pendant la même année, l'album concept, "Manifestation Of Fear" fut aussi publié et ils avaient préalablement fait une tournée en 1998 avec le groupe de metal américain Kamelot. En 2000, leur album "The Forbidden Fruit" fut enregistré et publié le 18 Septembre. Il y eut aussi l'arrivée d'un nouveau guitariste, Patrick Rondat, ex-membre de Jean Michel Jarre, et le départ de Chris Allister et de Henk Van der Laars.
Le nouvel album de Elegy traite de toutes les faiblesses de l'homme qui existent depuis des milliers d'années dans la recherche de l'ultime "Forbidden Fruit" (Fruit Défendu). Elegy placèrent consciemment une pièce maîtresse d'explosions musicales "métalisées", dans une folie mélancholique, pour attirer notre attention et reveiller des sentiments dont on ignorait l'existence.
Présentant le nouveau guitariste, Patrick Rondat, l'album fut enregistré au Excess Studio à Rotterdam et Günter Werno (Vanden Plas) qui participa en tant que musicien invité.