Amerykańska grupa powstała w 1987 w kalifornijskim Canoga Park. Heavy/powerowe pierwsze demo zawierało trzy numery: Invincible Metal, Self Made King i Society Of Victims. Te ponad 11 minut prezentowało Juliana Mendeza w niezłej formie - jego melodyjne power/speedowe zaśpiewy nieźle współbrzmiały z ulicznymi chórkami pozostałych. Prawdziwa siła leżała w duecie riffujących wspólnie gitar. Mendez wkrótce odszedł, a na jego miejsce gościnnie wskoczył John Bush z Armored Saint. Z nim w składzie Stone Soldier rozprowadził drugą demówkę. Znalazły się na niej dwie nowe kompozycje (Darkness i Love Or Confusion) oraz dwie nagrane ponownie (Self Made King i Invincible Metal). Kaseta cieszyła się nieco lepszą produkcją, na tle której głos Busha wypadł agresywniej i bardziej przekonująco od poprzednika. Wkrótce potem zespół zawiesił działalność.
John Bush dołączył potem w Anthrax.

Julian Mendez (ex-Heretic), John Bush (Armored Saint)