Йеспер Йенсен и Мортен Соренсен играли вместе еще в 80-х, однако под маркой Anubis Gate начали работать с 2001 года. На тот момент музыканты уже перепробовали различные виды тяжелого жанра, а в 21-м веке их потянуло на приправленный прогрессивом пауэр с влияниями таких коллективов, как Queensryche, Iron Maiden и Fates Warning. Первым делом Йеспер и Мортен взялись ваять демку, но если инструментальные партии они поделили между собой без проблем, то с вокалом дело обстояло хуже, и голос пришлось искать на стороне. К микрофону встал Торбен Аскхольм, ранее практиковавшийся как в трэше (Prophets Of Doom), так и в прог-металле (Northern Empire), а когда троица приступила к подготовке дебютного альбома, к делу подключились давние знакомые Йенсена и Соренсена, Хенрик Февре и Ким Олесен.

Материал заинтересовал представителей испанской конторы Locomotive Records, и после получасовой беседы с ними Anubis Gate обрели контракт. Дебютник "Purification" был скроен по канонам традиционного хэви, а прогрессивные фишки играли здесь второстепенную роль.

Практически все композиции были исполнены в среднем темпе и звучали мрачновато, но это объяснялось серьезной концепцией альбома, посвященной борьбе человека с внутренними демонами. Так или иначе, рынок принял работу датчан достаточно тепло, и ходившие в подмастерьях Февре и Олесен обрели в команде официальное членство. На сессии второго альбома группа вновь пригласила Якоба Хансена, но если в прошлый раз он еще играл на гитаре, то теперь в его руках сосредоточились только продюсерские функции. Структуры композиций на "A Perfect Forever" усложнились, темп стал более разнообразным, а некоторые обозреватели усмотрели в программе схожесть с Pagan's Mind. Скопировано с Dark-World.ru. В конце 2005 года Торбен сорвал голос, и в серии концертов пел Хенрик.

Впоследствии Аскхольм вообще выбыл из игры, а в 2006 году пост фронтмена занял Хансен. Якоб сохранил за собой и продюсерскую должность, однако при записи "Andromeda Unchained" ему в этом деле помогал Ким. Прогрессива на третьем альбоме стало еще больше, тексты приобрели научно-фантастический характер, а вкупе все новшества привели к более восторженным откликам.

В Дании "Andromeda Unchained" был номинирован сразу на три метал-премии "best album", "best production", "best cover", однако приз удалось взять только лишь обложке. Следующее творение Anubis Gate являлось логическим продолжением "Андромеды", разве что кое-где (например в копозиции "Pyramids") был использован восточный окрас, да общий концепт позаимствовали у известного автора видеоигр Мартина Рауффа (его сюжет адаптировал для внутренних нужд Февре).

"The Detached" проходил по тем же номинациям что и его предшественник, однако на этот раз тандем Хансен-Олесен сработал настолько четко, что награда группе досталась за продюсирование. Этим альбомом команда исполнила обязательства перед фирмой Locomotive, а когда готовился новый материал, к нему проявили интерес несколько других лейблов. Тем временем востребованность Хансена как продюсера резко возросла, и он принял довольно неожиданное решение покинуть группу.

На сей раз извне никого приглашать не стали, а микрофон перешел к уже проявлявшему себя в роли вокалиста Февре. Заключив контракт с американской конторой Nightmare Records, Anubis Gate стартовали на ней с одноименным альбомом, который хоть и унаследовал стилистику "Andromeda Unchained"/"The Detached", но получился более мрачным.