Le groupe a été créé à Genoa en octobre 1996. Sans perdre de temps, ils ont produit leur premier demo en décembre, qui contient quatre chansons: "Kingdom", "Out of the Darkness", "The Island" et "Storied Windows". Ce demo a aidé le groupe à se faire remarquer par la compagnie Underground Symphony. La formation au départ était formée de Wild Steel (vocal), Andrew Mc Pauls (clavier), Steve Vawamas (bass), Andre la Fisic (guitare) et Gianca (batterie). Avec l'aide de Frank Andiver et d'autres membres de Labyrinth, ils ont pu enregistrer leur premier album au Zenith recordings à Lucca, pour enfin voir le jour en novembre 1997.
En mars 1998, ils ont commencé à travailler sur un mini-album double, "Twilight". Il contient trois nouvelles chansons, une reprise de leur chanson "Fly Away" et des reprises de groupes américains des années 80. Lors de l'enregistrement, Frank Andiver, qui avait été également le producteur du premier album, est devenu officiellement un nouveau membre de Shadows of Steel, pendant que Andrew Mc Pauls quittait le groupe pour rejoindre Labyrinth. L'album "Twilight" a finalement été mis en vente en décembre 1998 et il y a eu la participation spéciale du guitariste Vic Mazzoni (Projecto) et du bassiste Andrea "The Tower" Torricini (Vision Divine, Wonderland). Le groupe s'est stabilisé avec l'arrivée de deux nouveaux guitaristes, Yackson et Ice Reaven. Par la suite, il y a eu une série de concert en Italie. Pendant ce temps, le clavieriste Francis Scarlet entre dans le groupe, avant de le quitter lors de l'hiver 2000. Toujours en 2000, ils ont mis en vente un single de quatre chansons du nom de "Heroes". Ils ont enregistré leur troisième album, “Second Floor “, entre 1999 et l'année 2000, mais en raison de quelques problèmes, ils ont seulement mis en vente le single.
Il aura fallu attendre en 2002 pour attendre la sortie de leur troisième album, "Twilight". Vers le début d'avril 2004, ils ont commencé l'écriture de leur quatrième album.