И только познакомившись с бывшим гитаристом блюз-роковой команды KASHMIR Дэвидом Стюартом (David Stuart), Стейси и Томми основали HALLOWS EVE. На роль барабанщика пригласили Тима Хелтона (Тут Helton), также в игравшего в WARRIOR, а еще раньше - в упомянутом PUBLIC ENEMY, a вторым гитаристом взяли некоего Скеллэйтора (Skellator), с которым друзья (Стейси и Томми) познакомились на Хэллоуин-вечеринке 1983 года, в день когда официально ушли из WARRIOR. В ту же знаменательную ночь придумали и соответствующее название для группы HALLOWS EVE.

Для Скеллэйтора HALLOWS EVE стала первой группой в его жизни, однако, он имел уже целую кассету с записанными на нее отдельными риффами и даже кусками песен. Аранжировкой идей Скелэйтора занялся Томми Стюарт, и через несколько недель HALLOWS EVE записали свое первое демо. Андерсон придумал название "Tales Of Terror", нарисовал обложку в духе комиксов ужасов и занялся распространением кассеты, которая принесла группе аж 500 долларов! Один из экземпляров "Tales Of Terror" попал в руки к шефу Metal Blade Records Брайану Слегелу (Brian Slagel), который, почувствовав в молодых музыкантах недюжинный потенциал, подписал с HALLOWS EVE контракт. Для начала Слегел включил одну из композиций - демо "Metal Merchants" - в шестую часть своего сборника "Metal Massacre", а пару месяцев спустя выпустил первый полнометражный альбом HALLOWS EVE, который так и назвали - "Tales Of Terror".

Незадолго до начала работы над пластинкой группу покинул барабанщик Тим Хелтон, а сразу после выхода альбома ушел Скеллэйтор, основавший потом LESTREGUS NOSFERATUS. За ударную установку усадили Ронни Эпполдта (Ronny Appoldt), a второго гитариста решили не брать вовсе. В таком виде HALLOWS EVE отправились в свое первое турне по стране, в ходе которого вначале открывали концерты NASTY SAVAGE и FATES WARNING, затем разогревали BLIND ILLUSION и AT WAR, а после завершения тура и до начала записи нового альбома дали еще ряд отдельных выступлений, играя на одной сцене с целым рядом звезд вроде MOTORHEAD, SLAYER, ANTHRAX, MEGADETH, KING DIAMOND, D.R.I., С. О. С. и DEATH!