Anno 1981 gründete der Gitarrist Jack Starr zusammen mit dem Schlagzeuger Joey Ayvazian in New York die Band Virgin Steele. Sie suchten nach einem Sänger und fanden David DeFeis über eine Zeitungsanzeige. DaFeis brachte auch Joe O'Reilly (Bass) mit in die Band.
Ihre erste Veröffentlichung war der Song „Children Of The Storm“ und erschien auf der „U.S. Metal Vol. II“-Compilation. Noch im gleichen Jahr veröffentlichten sie ihr selbstbetiteltes Debütalbum, welchens „Children Of The Storm“ als Titeltrack enthielt.
Das Zusammenspiel von DeFeis' Vorliebe für melodische Arrangements und Starr ist direkterer und härterer Art kam bei den Zuhörern gut an, doch kurz darauf, nach ihrem Nachfolger „Guardians Of The Flame“ und der Mini-LP „Wait For The Night“ gingen DeFeis' und Starrs Meinungen so weit auseinander, dass Starr beschloss, die Band zu verlassen.
Starr verlor in einem Prozess gegen den Rest der Band die Rechte am Bandnamen, und so engagierte David DeFeis seinen ehemaligen Schulfreund Edward Pursino, der Starrs Platz einnahm.
1985 erschien unter dem Namen Exorcist beim gleichen Label das Album „Nightmare Theatre“. Es kamen Gerüchte auf, dass Virgin Steele hinter dem unbekannten Bandnamen stecken würden, doch sie stritten es ab. Erst zwei Jahre später gaben sie es zu. In der Zeit konnten sie als Virgina Steele trotz Supportact von Manowar und guter Kritiken kaum Alben verkaufen und Bassist Joe O'Reilly verabschiedete sich.
Erst 1993 fanden sie einen würdigen Ersatz in Rob De Martino und unterschrieben bei der Plattenfirma Shark, wo sie noch im gleichen Jahr „Life Among The Ruins“ veröffentlichten.
Weitere Tours als Support von Manowar und Uriah Heep folgten, sowie weitere Alben, die sich deutlich besser verkauften. Unter anderem behandeln sie Sagen in ihren Diskographien, wie „The Marriage of Heaven and Hell“ oder „The House Of Atreus“.