História
A banda foi fundada em 1995, por Riku Hopeakoski (guitarra e teclados) e Mika Tönning (vocais), em Oulu. Conseguiu seu primeiro contrato com a gravadora Massacre Records, e logo após veio a divulgação da demo Winds, em 1997.
No ano seguinte, o grupo lançou seu primeiro álbum, o Halls of Frozen North, dando início a uma saga de quatro trabalhos de estúdio, onde cada tema era ligado ao outro por algum fato da história de cada álbum.
O segundo álbum foi lançado em 1999, o excelente Morning Crimson, quando conseguiram destaque entre as grandes bandas de Death Metal Melódico na Europa.
Após esse álbum os Catamenia sofreu algumas mudanças em seu line-up. Saiu o guitarrista Sampo Ukkola e o baterista Toni Tervo, e foram substituídos por Ari Nissilä e Sir Luttinen (Black League). Mas essa formação só durou às gravações do terceiro álbum, chamado Eternal Winter's Prophecy. Depois, o baterista Sir Luttinen e a tecladista Heidi Riihinen resolveram deixar a banda.
Em 2002, com a participação do baterista Janne Kusmin (Kalmah), e os teclados nas mãos de Riku Hopeakoski, o grupo volta destruindo tudo, com o seu mais forte álbum de estúdio, "Eskhata" .
Mais três álbuns foram lançados, o ChaosBorn, também considerado um dos melhores trabalhos da banda, com destaque na música “Calm Before the Storm “, Winternight Tragedies e o álbum Location:COLD.
Durante as gravações de Winternight Tragedies houve uma nova mudança na formação da banda: o vocalista Mika Tönning e o baixista Timo foram substituídos por O.J. Mustonen e Mikko Hepo-oja. Depois de uma tour de sucesso pela Europa, o baixista Toni Kansanoja junta-se à banda, depois da saída de Mikko.
Mais uma vez a banda teve problemas durante a gravação de um novo álbum. Após cantar quarto faixas O.J. Mustonen perdeu a voz e teve que ser substituído por Antti 'Hape' Haapsamo.
Mais tarde, depois do lançamento de Location: Cold, Kari Vähäkuopus tornou-se no novo vocalista.
Durante uma tour à Rússia Tero Nevala deixou a banda, que continuou a digressão sem tecladista.
Na Primavera de 2007 é a vez do baterista Veikko Jumisko abandoner a banda. Mikko Nevanlahti entra para o seu lugar.
Em 2008, foi lançado um novo álbum intitulado VIII – The Time Unchained. Cavalcade foi o álbum seguinte, lançado em 2010.
