Le groupe est formé en 1994 à Hämeenlinna et Tampere[1], et à l'origine connu sous le nom de Lords of the Left Hand, composé de Torog, Horns et Reaper. Ils publient une première démo intitulée Reality is in Evil en 1995. Après la sortie de la démo, le groupe change de nom pour Behexen en 1996[1].
En 1997, sous ce nouveau nom, le groupe publie sa deuxième démo, Eternal Realmin, suivie en 1998 par une troisième, Blessed Be the Darkness et enfin une quatrième, Support the War Against Christianity en 1999[2]. Dans l'année, Reaper quitte le groupe et est remplacé par Gargantum.
En 2000, le groupe publie son premier album studio Rituale Satanum. Environ trois ans plus tard, le groupe signe un contrat d'enregistrement avec le label finlandais Woodcut Records, et publie, en 2004, son deuxième album studio From the Devil's Chalice. Behexen tourne en Europe en 2005, avec Archgoat[3]. Ils publient ensuite un nouvel album, My Soul for His Glory, au label Hammer of Hate en 2008. Cette même année sort l'EP From the Devil's Chalice, et un split avec Satanic Warmaster.
En avril 2012, le groupe signe avec Debemur Morti Productions[4]. Après cinq ans sans nouvel album, le groupe révèle la pochette et la liste des titres de son quatrième opus, intitulé Nightside Emanations[5]. La pochette est réalisée par K. Lehto de Crimson Wine, et le layout par Helgorth de Babalon Graphics[5]. TIl est annoncé pour le 21 septembre en formats digipack et vinyle[5].
En mars 2016, le groupe révèle le titre de son nouvel album à paraitre courant l'année, The Poisonous Path[6]. L'album est mixé et masterisé par Tore Stjerna au Necromorbus Studio, et comprend un total de dix chansons[6],[7]. Il est annoncé pour, et publié, le 27 mai au label Debemur Morti Productions aux formats CD, vinyle et numérique[7]. Un premier extrait, intitulé Chalice of the Abyssal Water, est publié en avril 2016[7]. En juillet 2016, ils participent au Hellfest à Clisson, en France[8].