Группа «Catamenia» была создана в 1993 году в городе Оулу(Финляндия). Основателями группы стали Riku Hopeakoski и Mika Tonning. Первый демо диск вышел в 1995 году. На год позже, группа выпустила второй демо диск, под названием "Winds", после прослушивания которого менеджеры компании «Massacre Records» заключили контракт с группой. Дебютный альбом группы, под названием «Halls of Frozen North» (выпущенный в 1998) был записан в «Commusication Studios», во Франкентале (Германия) вместе с продюсером Gerhard’ом Magin’ом (Crematory, Heavenwood, Theatre of Tragedy). Этот альбом был признан критиками во всей Европе и принёс большую прибыль с продаж, учитывая что группа была малоизвестна. Комбинация кристально чистого Black-Metal'a и мелодичных звуков гитары была оценена на отлично. После этого у группы появились предложения о совместных турах с Dimmu Borgir, Death, Morbid Angel и другими не менее известными группами, но они были все отменены группой "Catamenia".

Второй альбом был записан в Швеции, на «Sunlight Studio» в Стокгольме. Произошло это в 1999 году, и называется он «MORNING CRIMSON». Этот альбом более тяжёлый, и более быстрый чем предыдущий, и он привлёк очень много поклонников, и записал группу «Catamenia» в историю Black-Metal'a. После записи этого альбома группу покинули гитарист Sampo Ukkola и барабанщик Toni Tervo были соответственно заменены на Ari Nissila и Sir’a Kimmo Luttinen’a.

В новом составе музыканты записали 3-й альбом, под названием «ETERNAL WINTER'S PROPHECY», который помог им забраться на вершину скандинавских хит-парадов, и позволил окончательно укрепится в «первом ряду» Black-Metal групп. На альбоме «ESKHATA» группа приходит к нам как квартет, из-за того что Sir Luttinen и Heidi Riihinen покинули коллектив. В записи этого альбома группе помогал клавишник Janne Kusmin, который не является официальным членом коллектива.
Альбом «ESKHATA» был впервые записан в родном городе группы, в Оулу на «SoundMix» студии. Он показывает совершенные навыки и мастерство исполнения группы, на много превышающие их ранние творческие успехи.