Enslaved s'est formé en 1991, par le duo Ivar Bjørnson et Grutle Kjellson, toujours dans le groupe actuellement. Ces derniers n'avaient alors respectivement que 13 et 17 ans. Le nom du groupe, "Enslaved", est tiré d'un morceau d'une démo de Immortal : "Enslaved in Rot".

A l'époque, le batteur Trym Torson les rejoignit, et ensemble, ils enregistrèrent leurs premières démos "Nema" et "Yggdrasil", respectivement en fin 1991 et durant l'été 1992. Alors qu'ils travaillaient sur leur premier vrai album, ils eurent l'occasion de sortir un split-CD avec Emperor en 1993 : "Hordanes Land". Ce mini-CD a été réédité par Candlelight Records avec le premier album du groupe : "Vikinglir VEldi" (initialement sorti sur le label d'Euronymous, Deathlike Silence Productions), au printemps 1994.

Enslaved a par la suite changé de label pour venir s'installer chez Osmose Productions, basé en France. "Frost", le deuxième album, sort donc rapidement sur ce même label, à la fin 1994. Enslaved a alors commencé à être connu en dehors de la sphère Black underground de Norvège. En résulta la tournée européenne "Winter War Europe Tour '95", ainsi que la toute première tournée d'un groupe de Black Metal aux Etats-Unis, au Mexique et au Canada durant l'année 1995. Ces tournées remportèrent un grand succès. Mais peu après, Trym quitta le groupe pour rejoindre Emperor.

En 1996, "Eld" fut enregistré avec Harald Helgeson à la batterie, et est sorti l'année suivante. Pourtant, le groupe ne pouvait jouer avec Harald de façon permanente, c'est pourquoi Dirge Rep et R. Kronheim rejoignirent le groupe, devenant des membres à part entière lors de l'enregistrement de "Blodhemn", en 1998.

Enslaved sortit une pièce importante en 2000 avec "Mardraum (Beyond the Within)", qui marqua un tournant pour le groupe. Cet album eût l'effet d'une véritable onde de choc dans le monde extrême, avec une approche du genre totalement innovante et expérimentale. C'est dans la même lignée qu'est sorti "Monumension" en 2001. Le groupe fut de nouveau impressionné par la réponse positive du public à leurs expérimentations et à leur approche du metal extrême. De nombreux concerts ont par la suite été donnés à un public norvégien, européen et américain toujours plus important et fidèle.

C'est en revenant du Royaume-Uni en mars 2002 que R. Kronheim dut quitter le groupe. Enslaved travaille alors sur leurs prochaines compositions, qu'ils décrivent désormais comme une synthèse entre leur thèse traditionnelle (leur coté Black Metal) et leur anti-thèse (leur coté progressif et expérimental). "Below The Lights" a ainsi été enregistré et est sorti en 2003. Cet album proposa un mélange parfait entre la puissance, la tradition, les éléments progressifs, et un coté sombre et psychédélique. Le processus et le travail engendré par cet album eurent raison du batteur Dirge, qui quitta alors le groupe.

Un nouveau line-up a donc été établi, avec Cato Bekkevold (fondateur de Red Harvest) et Herbrand Larsen. Avec tous ces changements laissés au passé, Enslaved atteignit de nouveaux sommets avec leurs prestations scéniques, en ajoutant notamment certains effets visuels qui ont permit au groupe de s'initier à la vidéo. Ils enregistrèrent ainsi leur premier DVD, intitulé "Live Retaliation".

Le groupe enregistra par la suite l'album "Isa" pendant l'automne 2004, qui est sorti juste après en Europe, et début 2005 aux Etats-Unis. L'album a reçu les honneurs dans tous les pays (sauf la Finlande apparemment !), et propulsa Enslaved à l'avant de la scène metal avant-gardiste contemporaine. Une grande tournée européenne avec leurs compatriotes de Vreid s'ensuivit en février et mars 2005, qui connut un franc succès. Durant cette tournée, le groupe reçu le Grammy Award norvégien ainsi que le Pris Alarm pour "Isa". Le groupe apparut ainsi sur plusieurs festivals et une tournée trans-américaine s'est déroulée à la fin 2005.

C'est en avril 2006 que le groupe "réapparait" avec leur dernier album en date, intitulé "Ruun". Le groupe continue le chemin tracé par "Isa", avec un son toujours plus contemporain, et un mélange entre musique extrême et musique progressive toujours plus fin, pour donner un tout d'une harmonie impressionnante. Les tournées qui suivent font logiquement la part belle aux trois derniers albums. Profitant d'une pause entre deux tournées courant 2008, Ivar Bjørnson, Arve Isdal et Grutle Kjellson, respectivement guitaristes et bassiste, se consacre à la sortie de Trinacria leur projet parallèle de black expérimental/atmosphérique à chant féminin.