Einherjer est formé en janvier 1993 par Frode Glesnes (guitare) et Gerhard Storesund (batterie) après la séparation de leur groupe Belzebub. Ensemble, avec le chanteur Rune Bjelland et Audun Wold, ils enregistrent une démo quatre titres la même année intitulée Aurora borealis. Un an plus tard, ils enregistrent en octobre 1994 au studio Lydloftet, l'EP Leve Vikingånden publié au label Necromantic Gallery Productions. En 1996, Audun Wold change de la basse à la guitare, le poste vacant étant repris par Stein Sund. Cette formation enregistre le premier album du groupe, intitulé Dragons of the North, publié au label Napalm Records, qui est suivi un an plus tard, par Far Far North au label Century Media Records. En 1998, le groupe est rejoint par Ragnar Vikse au chant et Erik Elden à la basse.
En janvier 2000 sort la démo Aurora borealis au label Necropolis Records. En 2003 sort leur album Blot au label Tabu Recordings[4]. Après onze ans et quatre albums, le groupe se sépare en [5]. En , tous les membres de la dernière formation d'Einherjer, dont les fondateurs Frode Glesnes et Gerhard Storesund, forment le groupe de thrash metal Battered avec le bassiste Ole Moldesæther.
En septembre 2008, Einherjer annonce se réunir pour une tournée en Europe en 2009, dont des participations au Ragnarök Festival, Kaltenbach et Wacken[6]. En janvier 2010, le groupe annonce son entrée en studio pour un nouvel album[7]. En , le groupe signe avec Indie Recordings, et annonce un nouvel album courant printemps 2011[1],[4]. L'album est enregistré au Studio Borealis, produit par Frode Glesnes et mixé par Matt Hyde ; il est annoncé en [8]. Einherjer jouera au John Dee d'Oslo le mercredi pendant l'Inferno Festival[8]. Einherjer annonce aussi sa participation aux festivals Karmøygeddon Metal, Brutal Assault, et Summer Breeze[8].
Le groupe revient en mars 2013 pour une tournée nord-américaine[9]. Ils feront notamment des passages à Québec, Montréal et Trois-Rivières, au Québec[9]. En , le groupe publie le clip de sa chanson Ballad of the Swords, illustrée par Costin Chioreanu[2].