Katatonia a été créé en 1991 à Stockholm, Suède et il a été formé par Anders Nyström (aka Blakkheim) et Jonas Renkse (aka Lord Seth). Après plus d'un an de travail et de composition, le premier disque est venu dans le milieu de 1992 avec la démo "Jhva Elohim Meth", enregistrée en Suède au Gorysound Studio et produit par Dan Swanö. La démo a été épuisée rapidement, ce qui attiré l'attention de la compagnie hollandaise Vic Records, qui a décidé de remettre en vente la démo en format EP du nom de "Jhva Elohim Meth – the Revival". Avec la popularité et la réputation qui augmentaient, le duo a décidé d'ajouter des membres au groupe. Alors, le bassiste Guillaume Le Huche (aka Israphel Wing) s'est joint à eux, ce qui leur a permis de jouer live pour la première fois de leur carrière.
Les choses se passaient bien et vers la fin de 1992, le trio a pu signer un contrat pour un disque avec la défunte compagnie suèdoise No Flashion Records. En avril 1993, Katatonia est entré à nouveau au Gorysound, maintenant renommé Unisound, pour enregistrer leur premier album, "Dance of December Souls", produit par Katatonia et Dan Swanö. Le tout ne semblait jamais prendre fin, mais le disque a finalement été disponible en décembre 1993. Le groupe s'éloignait de leur passé black metal afin d'offrir une mélancholie épique émotionnelle, il s'agit d'un grand chapître dans le style doom metal. Au début 1994, il retourne au Unisound pour enregistrer la pièce gothique épique de 10 minutes ‘Scarlet Heavens’. La pièce s'est éventuellement trouvée une maison avec Misanhropy Records qui ont mis en vente un 10" limité (avec Primordial en 1996).
Lors de l'été 1994, Wrong Again Records a approché le groupe pour qu'il participe à leur compilation, en plus d'avoir une offre de contrat de Avantgarde Music. Maintenant familié avec Unisound, ils enregistrent les pièces ‘Black Erotica’ et ‘Love of the Swan’ pour la compilation et ‘For Funerals to Come’ pour un EP à être mis en vente par Avantgarde Music au début 1995.
Katatonia a surpris tout le monde en prennant une sabatique l'année suivante. Les difficultés à Nyström & Renkse pour trouver un line-up stable a mené les deux musiciens à se concentrer sur d'autres projets. Renkse a fondé October Tide pendant que Nyström a divisé ses occupations entre Diabolical Masquerade et Bewitched.
Les deux membres ont ramené à la surface Katatonia au début 1996. Le guitariste Fred Norrman, anciennement de October Tide, s'est joint à eux pour entrer chez Unisound, mais cette-fois le trio n'avait rien écrit à ce stade. Après deux semaines d'enregistrement, Katatonia a créé l'album "Brave Murder Day". Mikael Åkerfeldt de Opeth a été invité à chanter sur le disque. Katatonia et la production de Dan Swanö a pu rendre justice au nouveau son du groupe. Proposant à la fois une ambiance fortement émotionnelle, ils ont influencé beaucoup la scène.
Suite à une tournée européenne à l'automne 1996, Katatonia est entré en studio en 1997 avec du nouveau matériel. Puisque Unisound a fermé ses portes, ils se sont tournés vers Sunlight Studio de leur ville natale, Stockholm. Le résultat a été le EP "Sounds of Decay", encore une fois par Avantgarde Music. Produit par le groupe et mixé par Tomas Skogsberg, le disque mettait encore en vedette le vocal de Mikael Åkerfeldt.
Par la suite, ils ont ajouté le bassiste Mikael Oretoft avant de retourner au Sunlight Studio au milieu de 1997 pour travailler sur leur troisième album, "Discouraged Ones". Cette fois, Renkse s'est occupé du vocal et de la batteur, alors Åkerfeldt a été le producteur. L'aspect gothic combinait également la perte et la désolation, le désespoir et l'espoir.
Peaceville Records a suivit la carrière du groupe depuis pratiquement le début, mais c'est avec "Discouraged Ones" et sa modernité et son dynamisme que la compagnie est tombée en amour avec leur son. La compagnie a offerte un contrat pour cinq albums. Katatonia était redevenu un trio et ils ont pu travailler sur leur quatrième album studio en 1999, "Tonight’s Decision". Il a été enregistré au Sunlight Studio et produit encore une fois par le groupe et Åkerfeldt continue de co-produire le vocal, en plus d'être assisté par Tomas Skogsberg au montage. Le producteur/monteur Dan Swanö s'est occupé de la batterie en studio, afin que Renkse se concentre totalement sur son vocal. Avec une large distribution internationnale, ils ont fait une tournée avec Paradise Lost avec un nouveau membre, le frère de Fredrik Norrman, le bassiste Mattias Norrman et Daniel Liljekvist à la batterie.
En 2000, ils ont enregistré leur cinquième album en plus de visiter la Pologne et les États-Unis en compagnie de Opeth pour des spectacles, Katatonia a mis en vente "Last Fair Deal Gone Down" lors de l'été 2001. La sortie du disque a été suivit d'un single de trois pièces, "Teargas". Après plusieurs spectacles en Europe, ils ont mis sur le marché le EP "Tonight's Music". Ce disque contient les pièces exclusives "Help Me Disappear" et "O How I Enjoy the Light".
Lors de l'année 2002, le groupe a préparé leur prochain album. En avril 2003, ils ont mis sur le marché leur sixième album, "Viva Emptiness", l'album a été enregistré au 301 Studios à Stockholm et Fascination Street à Örebro à la fin de 2002. Produit par Nyström/Renkse et mixé par Jens Bogren. Ils ont fait une tournée européenne en avril et mai 2003.
En 2004, Katatonia a fait une grande quantité de spectacles, qui a été complété par le début du travail du prochain album. En 2005, il y a eu deux compilations qui ont été mises en vente. La première par Avantgarde Music qui se nomme "Brave Yester Days", qui couvre 1992 à 1997. Il contient deux disques et il possède des pièces de démos, singles, compilations en plus des meilleurs moments des deux premiers opus. La seconde compilation, "The Black Sessions", mise en vente par Peaceville, contient deux disques couvrant l'ère 1998-2004, en plus d'un DVD filmé en Pologne en 2003 durant la tournée Viva Emptiness.
En 2006, Katatonia propose le single "My Twin", en plus d'un vidéoclip pour la même pièce sous la direction de Charlie Granberg. Leur septième album, "The Great Cold Distance", a été enregistré lors des trois mois de l'été 2005 au Fascination Street Studios, Örebro, Suède. Il est mis en vente le 13 mars 2006. Le single "Deliberation" est mis sur le marché le 15 mai de la même année. Katatonia fait plusieurs spectacles afin de promouvoir le disque, dont une tournée en Amérique du Nord avec Moonspell. Ils sont de passage à Québec le 24 octobre 2006.