Le projet de The Storyteller commença en 1995 avec L-G Persson (chanteur) et Fredrik Groth (guitariste), et à cette époque, le concept était un peu différent de ce qu'il est aujourd'hui. La musique était strictement acoustique avec plusieurs choeurs. Pas très metal, mais vraiment excellent! Après quelques mois, Magnus Björk (chanteur) et Jocke Lundström (guitariste/chanteur) joignirent le groupe. Un démo consistant en trois chansons, "Kingdom Above", "Power Within" et "Chant Of The Thieves", fut enregistré dans un studio local. Deux des chansons furent ré-enregistrées plus tard pour le premier album de Storyteller. À cette époque, le groupe ne s'appellait que Storyteller, le "The" fut rajouté presque cinq ans plus tard.
Quelques cassettes démo avec une très laide couverture noir et blanche furent envoyées à quelques compagnies suédoises, mais cela ne donna aucun résultat, car les compagnies pensaient que les paroles auraient dûes être en suédois. À la place, les démos furent vendus à des amis et des connaissances. À cette époque, le groupe n'avait jamais joué "live".
Dans le milieu de l'année 1996, Fredrik ressentit que Storyteller se dirigeait dans une direction qu'il n'aimait pas, alors il quitta le groupe temporairement pour travailler de son côté. Un autre guitariste (Per Nilsson) joignit le groupe, et, à cause des forces de tout ces musiciens différents, Storyteller avec une sonorité très étrange à ce moment. Jocke Lundström jouait maintenant de la batterie au lieu de la guitare. Un nouveau démo fut enregistré, avec à peu près les mêmes chansons que sur le premier démo, mais avec "Like A Wind" au lieu de "Chant Of Thieves". L-G détestait de plus en plus la situation musicale et, durant l'année 1997, Storyteller disparu en quelque sorte pendant un certain temps, à cause du manque d'intérêt du groupe.
En Décembre 1997, Fredrik se mit avec L-G à nouveau et ils décidèrent d'avancer la musique une étape plus loin, et ils trouvèrent un nouveau batteur, Martin Hjerpe. Ils remplacèrent également leurs guitares accoustiques avec des guitares électriques. Inspirés par des groupes heavy metal allemands comme Helloween et Blind Guardian, ils ré-arrangèrent leurs vieilles chansons et écrivirent un peu de nouveau matériel L-G et Fredrik réalisèrent rapidement que c'était ce qu'ils avaient toujours voulu faire! Du heavy metal pur!
La première pensée fut que L-G devrait seulement chanter, donc Storyteller avait besoin d'un bassiste... et Anders Östlin les joignit pendant un bout. Pendant cette période, Per eut un problème avec ses bras et ne pouvait pas jouer du tout. Il était toujours dans le groupe cependant, pendant qu'il allait se rétablir. (Note: aujourd'hui, presque quatre ans après, Per ne peut toujours pas jouer)
En Avril 1998, Storyteller enregistrèrent un nouveau démo consistant en trois chansons, "The Unknown", "Power Within" et "Sense Of Steel", et l'envoyèrent à quelques compagnies de disque allemandes et japonnaises. L'une d'entres elles, Noise Records en Allemagne, répondit aussitôt qu'ils reçurent le CD, et leur dirent qu'ils aimaient beaucoup la musique, mais qu'ils n'aimaient pas du tout le chanteur et qu'ils devaient écouter plus de chansons. Préférablement avec un autre chanteur.
Panique totale! Deux chansons de plus furent écrites et enregistrées, "Guardians Of Kail" et "Book Of Mystery", et envoyées à Noise, toujours avec L-G comme chanteur. Cette fois-ci, ils n'avaient pas l'air du tout autant interressés que la première fois qu'ils répondirent, et ils dirent à Storyteller qu'ils avaient réellement besoin d'un nouveau chanteur.
Alors, Storyteller abandonnèrent et écoutèrent la compagnie. L-G décida qu'il ferait la basse au lieu de chanter, et Anders Östlin fut "dégradé" en tant que claviériste. Quelques mois après, il quitta le groupe.
La musique de Storyteller sonnait maintenant presque comme les débuts de Helloween, et ils étaient à la recherche d'un nouveau chanteur pour aller avec leur style. Ce ne fut malheureusement pas facile de trouver un bon chanteur metal! Plusieurs chanteurs furent testés, quelques uns d'entres eux n'étaient vraiment pas bons et quelques autres n'allaient tout simplement pas avec la musique que Storyteller jouait, alors c'était L-G qui chantait la plupart du temps dans les spectacles.
Ils avaient aussi besoin d'un autre guitariste, comme ça ne fonctionnait pas avec un seul guitariste dans le groupe. Plus tard, ils se rendirent compte qu'un des chanteurs testés (Lasse Martinsen) était un bien meilleur guitariste que chanteur, alors il joignit le groupe en tant que guitariste à la place!!! Et quand L-G décida de prendre le microphone à nouveau, environ un an après l'avoir abandonné pour la première fois, Storyteller était complet!
Le groupe fit plusieurs spectacles et enregistra quelques autres démos, ils écrivirent plusieurs bonnes chansons, et quelques autres assez ordinaires... Plusieurs démos furent envoyés à des compagnies, et finalement, en Juin 1999, Storyteller eurent leur tout premier contrat de disque!!! No Fashion et House Of Kicks montrèrent leur intérêt, et seulement quelques jours après qu'ils aient entendu le démo, un contrat fut signé!
Trois semaines en Septembre et Octobre 1999, Storyteller enregistrèrent leur premier album dans le légendaire Studio Fredman à Gothenburg en Suède. Plusieurs bons groupes comme In Flames, The Haunted, Hammerfall, Dimmu Borgir et At The Gates ont enregistré plusieurs de leurs album là. Peu après les enregistrements, le guitariste Lasse Martinsen fut remplacé par Erik Gornostajev.
Le premier album de Storyteller fut publié en Europe en Mai 2000 et reçut plusieurs tonnes de bonnes critiques, mais pas beaucoup de mauvaises. Pendant l'année 2000, le groupe joua aussi à plusieurs occasions. À un spectacle en Octobre, Joacim Cans et Oscar Dronjak de Hammerfall joignirent The Storyteller sur la scène et jouèrent une reprise de la chanson "Black Wind Fire And Steel" de Manowar, juste pour le plaisir.
Rendu à ce point, l'album n'était toujours pas sorti au Japon, quelques personnes l'importèrent donc... En fait, l'album fut listé dans la charte des "Albums Importés" du magazine japonnais Burrn six mois d'affilée! (Les rangs étaient: Août: #5, Septembre #3, Octobre #3, Novembre #24, Décembre #49, Janvier #42.) Mais finalement, en Décembre, l'album fut officiellement publié au Japon par la compagnie Soundholic Co. Ltd. Comme ils ne pouvaient pas s'en tirer sans chanson bonus, le premier démo acoustique de "Chant Of The Thieves" fut ajouté.
Pendant l'année 2001, le groupe fit plusieurs concerts et composa du nouveau matériel pour leur futur album. Une fois de plus, il fut décidé qu'ils allaient l'enregistrer au Studio Fredman, qui est simplement le meilleur studio heavy metal en Suède. (Selon nous, bien-sûr) Deux semaines avant l'enregistrement, Erik Gornostajev quitta le groupe à cause de raisons personnelles, donc le groupe commeça immédiatement à chercher un nouveau guitariste, et ils trouvèrent un gars du nord de la Suède nommé Pärka Kankanranta. Malheureusement, il n'allait pas bien dans le groupe, mais il fit trois solos de guitare sur les enregistrements, ainsi que deux spectacles avec le groupe. Dans le début d'Août 2001, un nouveau guitariste du nom de Jacob Wennerqvist joignit le groupe.
En Octobre 2002, Janne Björk quitta le groupe, et comme le groupe se concentrait sur l'écriture du matériel pour leur troisième album, ils décidèrent de remettre les recherches à plus tard. L'album fut enregistré pendant Mars et Avril 2003, devinez où? Oui! Au Studio Fredman. Après avoir fini les sessions d'enregistrement, le groupe se mit à la recherche d'un nouveau bassiste, se retrouvant avec un guitariste appelé Johan Sohlberg à la basse pour l'apparition au Sweden Rock Festival le 8 Juin. Après le festival, le groupe retourna au Studio Fredman pour faire le mixage final de l'album. Après cinq mois calmes, la sortie de "Tales Of A Holy Quest" sortit le 27 Novembre, suivi par une fête de lancement et un concert le 29 au Musikhuset/Gävle.
À cette époque, les plans pour faire un vidéoclip sur la chanson "Seed Of Lies" du nouvel album furent développés et décidés. Le vidéoclip fut filmé dans le milieu du mois de Janvier pendant 4 jours pris entre la chaleur de lumières du studio et les vents froids de l'hiver suédois à l'extérieur. Plusieurs remerciements à tout les volontaires qui ont souffert et se sont gelés les extrémités dans le froid intense! Aussi, il est bien de mentionner le producteur Lennart Jonsson et le directeur Israel Benavides sans qui le vidéoclip aurait été "mission impossible"! Le vidéoclip fut présenté officiellement pour la première fois à la fête de lancement le 12 Mars 2003 au Club Monster à Gävle et est diffusé sur Z-TV parmis plusieurs autres chaînes.
Pendant la première moitié de l'année, le groupe joua quelques concerts occasionnels dans les petits clubs, supportèrent Bruce Kulick et Rockland à Sala, et après avoir pris leur Été de vacances, se réunirent pour un spectacle au festival Gates Of Metal à Hultsfred le 31 Juillet. Quelques jours avant le spectacle, un CD contenant "Seed Of Lies" en tant que piste CD et vidéoclip aussi, une reprise de Ozzy Osbourne, "Bark At The Moon", une version "live" de "The Secrets Revealed" et une chanson démo appelé "Prophets Of Liars" fut lancé.
