AXENSTAR založili Petr Johansson (kytara) a Magnus Ek
(basa) jako covermetalovou skupinu v roce 1998 pod názvem POWERAGE. Zpěvák v té době byl "Pan.Eddie", bubeník a sólový kytarista v tom čase, byl Johan Burman jako záskok z Chemical Co-operation a Magnus Soderman z Lost Souls.

Jediné vydání POWERAGE v této sestavě byl tribut (cover) IRON MAIDEN. "Hallowed be thy name" bylo nahráno a vydáno na "Made in Scandinavia" (Tribute Records). V roce 1999 byl Eddie nahrazen Magnusem Erikssonem (vokály, klávesnice) a Magnusův bratr Thomas "naskočil" na sólovou kytaru. Pontus Jansson zaujal místo jako bubeník v POWERAGE ve stejném čase.

Po seskupení, které bylo kompletní, skupina začala psát písně společně se zaměřením na silných melodiích a heavy kytarové rytmické džezové figuře. V březnu 2000 vstoupili do studia "Studio Underground" ve Västerås, ve Švédsku k tomu, aby nahráli své první demo CD "The Beginning". Čtyři písně byly nahrány a začali to posílat nahrávacím společnostem. Dostali nějaké nabídky, ale žádný z kontraktů nebyly podepsány. "The Beginning" dostal vynikající recenze ve švédském Metal tisku.

POWERAGE hráli nějaké místní živé vystoupení se skupinami jako The Storyteller a Stormwind jen abychom jmenovali alespoň některé. V lednu 2001 byly nahrány dvě nové písně, "Confess Thy Sins" a "Seventh Labyrinth". V březnu 2001 změnili své jméno na AXENSTAR. V srpnu 2001 skupina ještě jednou vstoupila do studia, tentokrát v Studio Sutare, aby bylo nahráno nové demo. Jednoduše pojmenované "promo 2001". Tentokrát byly nahrány tři písně, "Confess Thy Sins", "King of Tragedy" a "The Cross We Bear". Znovu poslali demoverzi, aby přitahovala pozornost nahrávacích společností a tentokrát dostali nabídku, kterou nemohli odmítnout. Podepsali se španělským labelem Arise Records a pustili se do práce na svém debutovém albu "Perpetual Twilight". Album bylo vydáno v říjnu 2002 a dostalo opravdu dobré recenze po celém světě.

Druhé album, "Far From Heaven", bylo vydáno jen o rok později, v listopadu 2003. Mezitím, Axenstar také měli čas na to hrát vícekrát živě včetně Motala Metal Festival 2002, Sweden Rock Festival 2003, a evropské turné spolešně s Falconer a Doomsword.

Své třetí album vydali v květnu 2005 pod názvem "The Inquisition". Nahrávání a míchání alba zvládli tentokrát v Underground Studios. O mastering alba se postaral Peter in de Betou (Amon Amarth, Hypocrisy). Obal desky udělali u Toxic Angel (Sonata Arctica, Children Of Bodom).

V listopadu 2005 se Thomas Eriksson & Peppe Johansson rozhodli opustit skupinu "kvůli osobním důvodům", diskuze k této věci trvaly dlouho a nakonec se rozhodli, že toto bylo nejlepší řešení pro všechny zapojené lidi. Joakim Jonsson (Skyfire, The Mist Avalon) se bude starat o kytary pro skupinu. Na konci roku 2005 podepsali smlouvu s Massacre Records.

U nového labelu a s novým kytaristou započali v dubnu 2006 práci na novém čtvrtém albu. CD vyšlo v září téhož roku pod názvem "The Final Requiem". Podle skupiny to bylo zdaleka nejtěžší vydání v historii Axenstar.

V prosinci 2006 opustili skupinu basista Magnus Ek a bubeník Pontus Jansson. Nahradili je Thomas Ohlsson (bicí) a Henrik Sedell (basa).