En 1996, c'est le guitariste Mikael Fitrzyk qui a formé le groupe Invictus, connu sous le nom QUARK7 à l'époque. Ils avaient Yngwie Malmsteen, UFO et Savatage surtout comme influence et ils jouaient un style plus progressif, symphonique et mélodique. Après quelques changements, QUARK7 font leur premier album, Fly Away, mais ils n'ont pas eu l'attention qu'ils désiraient. En 1999, ils produisent Once Upon A Time, ils ont financé l'album par eux-même. Avec cette album et un site avec 12 langues différentes, ils ont eu l'attention de quelques compagnies. Ils ont eu des critiques dans des magasines en Norvège, au Japon, en Angleterre, en Allemagne, en Suède et au Brésil pour finalement signer une entente avec la compagnie. En février 2002, ils vont au Melody Studios à Paris pour enregistrer leur troisième album, Black Heart (le premier album sous le nom Invictus). Didier Chesneau a été le producteur et A. Ribot (clavier) et S. Grare (vocal) ont fait une prestation spéciale sur l'album. Par la même occasion, ils signent un contrat avec la compagnie Limb Music.