Era verão de 1996 quando André Fabian, Culver Yu e Anderson Xavier, durante um período de férias, trocaram ideias sobre música e chegaram a uma decisão definitiva: formar uma banda que fosse mais do que apenas um passatempo. Todos já haviam tocado em outros grupos e queriam que essa nova experiência fosse levada a sério, com identidade própria e visão de futuro.
O ponto em comum entre eles era o Heavy Metal. Não qualquer abordagem, mas sim o metal europeu clássico, melódico, veloz e épico, com passagens marcantes e temas grandiosos, sem abandonar o peso característico do estilo. A partir dessa proposta nasceu também o nome que definiria a banda: Steel Warrior, um guerreiro de aço que simbolizava tanto a estética heroica de suas composições quanto a resistência do gênero diante dos modismos passageiros.
Com André Fabian nas guitarras e vocais, Anderson Xavier no baixo e Culver Yu na bateria, a banda ainda buscava um segundo guitarrista. Após várias tentativas, encontraram Robert Nietsche, que, mesmo com pouca experiência, compartilhava dos mesmos ideais musicais. Assim se consolidou a formação inicial e começaram a surgir as primeiras músicas.
Entre as composições iniciais estavam Wind of Sorrow, uma balada com clima trágico ambientada na Inquisição, Rasalom, inspirada em The Keep, além da faixa-título Steel Warrior, que sintetiza a alma da banda. Outras músicas, como Blind Faith e Crossing the Mist, ampliaram ainda mais a identidade épica e melódica do grupo.
Após a estreia ao vivo em outubro de 1996 na Iª Heavy Metal Convention de Itajaí, a banda começou a conquistar reconhecimento regional. Em seguida veio a Demo Tape com as faixas Rasalom e Steel Warrior, recebendo críticas positivas e chamando atenção da imprensa especializada e de fãs do Brasil e de outros países.
Mais tarde, com Pedro Giovani assumindo a guitarra, a Steel Warrior seguiu evoluindo, abriu show para o Gamma Ray em Florianópolis e consolidou o repertório que daria origem ao debut álbum Visions from the Mistland, um trabalho forjado com muito sacrifício, paixão e fidelidade à essência do Heavy Metal.