Музыкальная деятельность Йонаса Ренксе и Андерса Нистрёма началась ещё в 1987 году, когда последнему было 13 лет. В те времена музыканты играли блэк-метал, имевший существенные влияния групп Celtic Frost и Bathory. Никаких записей той группы не сохранилось, да и сама она вскоре распалась. На остатках распавшейся музыкальной формации образовался музыкальный коллектив Katatonia, который начал свою деятельность в 1991 году в формате дуэта. Основали группу Йонас «Лорд Сет» Ренксе (вокал, ударные) и Андерс «Блэккхейм» Нистрём (гитара). В этом же году, летом, участники записали демо Jhva Elohim Meth, которое за пару недель разошлось полным тиражом в 400 копий. Музыкально демо сочетало в себе звучание блэк-метала и дум-метала, а лирически было посвящено суицидальным темам.
Не знаю, откуда все это берется, честно, не знаю… Когда мы с Андерсом начинали заниматься музыкой, мы хотели создать нечто безумно мрачное, настолько депрессивное, насколько это только возможно. Мы сами, в принципе, никогда не были особо счастливыми людьми… и оттого сильно напрягаться не пришлось. Нужно было просто излить свою душу, высказать несколько привычных мыслей. …Я часто думаю о том, как можно «уйти» из этой жизни, периодически чувствую жгучее желание совершить самоубийство… только вот до сих пор не уверен, так ли уж приятно быть мертвым.
Музыка группы очень быстро привлекла к себе внимание, а некоторые критики даже назвали Katatonia самой депрессивной группой планеты. Другие же характеризовали музыку коллектива как смесь Paradise Lost и Bathory, третьи называли блэковым Tiamat. Немногим позже это демо было переиздано на аудиокассете голландским лейблом Vic Records, и за четыре недели было продано более 1000 копий релиза. Чуть позже состав подкрепился бас-гитаристом Гуиламом «Израфель» Ле Хуче, и команда смогла отыграть свой первый концерт в шведском городке Бро. В то же время Katatonia подписывает лейбл No Fashion Records и участники отправляются в студию Unisound для записи дебютного альбома.
Первый полнометражный альбом Dance of December Souls был издан в 1993 году лейблом No Fashion Records, в дальнейшем Katatonia отыграла серию концертов у себя на родине. Некоторые в лирической части альбома увидели ярко выраженные дяьволопоклоннические мотивы. В начале 1995 года, помимо появлений на публике, команда заключила контракт с Avantgarde music, записала EP For Funerals to Come, выпущенный лимитированным тиражом в 300 копий в виде пикчер диска (picture disc) и приняла в свои ряды второго гитариста Фреда Норрмана. Лирически, да и музыкально, релиз недалеко ушёл от своего предшественника. Однако в музыке уже наметились готические веяния, а также появился чистый вокал (правда, только в двух композициях).
В дальнейшем Katatonia приступает к записи второго полноформатного альбома, однако состав команды покидает басист Израфель. Его место занимает Фредрик Норрман, а для записи «рычащего» вокала приглашается Микаэль Окерфельдт из Opeth. Вскоре Katatonia вновь появилась на сцене (в составе Нистрём, Ренксе, Норрман). Контракт с Avantgarde Music были продлён, и в 1996 году лейбл издал второй полноформатник Brave Murder Day, после чего шведы отправились на европейские гастроли. В ходе турне интерес к коллективу проявила компания Century Media, взявшаяся за издание Brave Murder Day в США. Отличительной особенностью оформления релиза явилось то обстоятельство, что тексты песен были написаны сплошным текстом и никак не подразделялись на композиции. Музыкально же наметилось ещё большее смягчение звука, в том числе использования чистого вокала и акустических гитарных вставок.
В том же 1996 году вышел сплит Katatonia с группой Primordial, на котором Katatonia представили свою новую композицию «Scarlet Heavens». В 1997 году в команде появился новый басист Микаэль Оретофт, при участии которого были записаны два миньона (Sounds of Decay и Saw You Drown) и один альбом. В Sounds of Decay ещё можно было услышать гроулинг и низко настроенные гитары. После выхода данного релиза Katatonia меняет свой логотип. Saw You Drown уже наметил будущие музыкальные изменения, которые можно услышать на грядущем альбоме — в частности, гроулинг сменился чистым вокалом. Наконец альбом Discouraged Ones окончательно запечатлел произошедшие с группой изменения, из-за чего многие поклонники коллектива отвернулись от творчества Katatonia. К концу 1998 года Katatonia заключила пятиальбомный контракт с Peaceville Records, но при этом вновь осталась без бас-гитариста.
В 1999 году состав группы пополняется новым участниками — Даниэлем Лильеквистом (ударные) и Маттиасом Норрманом (бас). В том же году Katatonia записывала очередной альбом Tonight’s Decision и путешествовала по Скандинавии, сопровождая Paradise lost. Новый альбом отличался большим уклоном в смешивание различных жанров: в частности, на нём можно слышать элементы альтернативного метала, гранжа и прогрессивного рока.
Пока «Peaceville» выпускала Tonight’s Decision, группа уже подготовила следующую пластинку, а также приняла участие в фестивалях, проходивших в Польше и США. В 2001 году в свет вышло два миньона, Teargas и Tonight’s Music, а также полноценный альбом Last Fair Deal Gone Down. Но помимо студийной работы группа уделяла внимание и гастрольной деятельности, совершив европейский тур на разогреве у Opeth. Сделав небольшую передышку, Katatonia вновь занялась подготовкой свежего релиза.
На этот раз сессии проходили в двух местах, «Studio 303» и «Studio Kuling». Viva Emptiness был издан Peaceville Records в апреле 2003-го. Диск в очередной раз доказал, что Katatonia осталась верна своему стилю и не нуждается ни в каких экспериментах. Остаток года и начало следующего команда провела на европейских гастролях в качестве хедлайнера.
В 2006 году Katatonia выпускает очередной альбом The Great Cold Distance. Позже две композиции с этого альбома, «Deliberation», «My Twin» и «July» вышли отдельными синглами в 2006 и 2007 годах.
Начиная с 2008 года Katatonia приступает к работе над новым альбомом, который чуть позже получит название Night is the New Day. В целом альбом выполнен в том же ключе, что и его предшественник, с разве что небольшими изменениями в партиях ударных и чуть большим использовании бэк-вокала. Также характерно для этого альбома полное отсутствие гроулинга (хотя ещё на предыдущей работе в «The Itch», «Leaders», «July» его можно было услышать). Темп и тяжесть песен понизились, появилась чисто акустическая «Idle Blood» и безгитарная «Departer», ставшая на альбоме заключительной. Официально альбом вышел в Европе 2 ноября 2009 года, выпускающим лейблом снова стал Peaceville Records. До США он добрался 10 ноября.
Через некоторое время была оглашена новость о новом туре, а 22 декабря 2009 года поклонники Katatonia получили шокирующее известие — братья Норрманы — Маттиас и Фредрик — объявили об уходе из группы, мотивировав это семейными причинами. Замена ушедшим музыкантам нашлась быстро. Место Фредрика занял гитарист Bloodbath, параллельно много лет работавший техником в группе — Пер «Sodomizer» Эрикссон; Маттиаса заменил Никлас «Nille» Сандин.