Вскоре после краковского концерта Gorgoroth покинули Nuclear Blast. Тогда же из группы ушёл ударник Квитрафн. Его должен был заменить Фрост, однако он не смог совместить работу в Gorgoroth и Satyricon.

В течение 2004 года Gorgoroth провели турне по Южной Америке, причём концерт в Сальвадоре сопровождался беспорядками, впервые выступили на Inferno Metal Festival (апрель 2004 года), осенью дали ряд концертов в Европе и Центральной Америке. Для осенних выступлений были приглашены концертные музыканты — гитарист Телох (Teloch) и ударник Дёрж Реп (Dirge Rep; настоящее имя Пер Хусебо, бывший ударник Enslaved). В 2005 году выступления продолжились.

Седьмой студийный альбом Ad Majorem Sathanas Gloriam вышел на шведском лейбле Regain Records 19 июня 2006 года. Запись альбома растянулась больше чем на год — с января 2005 года. Сессионным ударником снова был Фрост, игравший в группе ещё в 1994—1995 годах. Ad Majorem Sathanas Gloriam достиг 22-го места в норвежских чартах и был номинирован на главную норвежскую музыкальную премию Spellemannprisen как лучший металический альбом, но премия досталась альбому Enslaved Ruun. На песню «Carving a Giant» был снят первый за историю существования группы видеоклип. 27 июня 2006 года Кинг ов Хелл ушёл из группы, как было объявлено, из-за идеологических разногласий. В интервью, данном месяц спустя, Кинг подтвердил, что причиной ухода стали проблемы, которые он испытывал, поддерживая имидж Gorgoroth на публике.

Весной 2006 года Гаал снова сел в тюрьму, на этот раз за избиение 41-летнего мужчины и угрозы выпить его кровь, произошедшие ещё в 2001 году. Решение было вынесено в 2004 году: Гаал был приговорён к 18 месяцам тюрьмы и штрафу в пользу потерпевшего в 104 000 норвежских крон. После обжалования срок был уменьшен до 14 месяцев, а штраф увеличен до 190 000 крон. Запись вокала и написание текстов для Ad Majorem Sathanas Gloriam проходили в течение двух недель непосредственно перед тем, как Гаал должен был отправиться в тюрьму. Он вышел на свободу в декабре того же года.

Одновременно с Гаалом Инфернус отбывал срок за изнасилование. В мае 2005 года Инфернус и его друг получили по три года тюрьмы и по 155 000 крон штрафа (в том числе по 55 000 крон в пользу потерпевшей). После апелляции с Инфернуса были сняты обвинения в изнасиловании, но он был признан виновным в сексуальном домогательстве с отягчающими обстоятельствами. Приговор его друга был оставлен в силе. В марте 2007 года Инфернус досрочно вышел на свободу.

Кинг снова стал постоянным басистом группы, а в январе 2007 года представлял Gorgoroth на промоакции в Лос-Анджелесе.

Раскол

В октябре 2007 года Инфернус опубликовал на своей странице MySpace сообщение, в котором говорилось, что группа распалась, и Инфернус с одной стороны и Гаал и Кинг с другой стороны будут работать самостоятельно. При этом нерешённым остался вопрос о правах на имя группы. В тот же день Гаал и Кинг опубликовали аналогичное сообщение, которое в частности содержало заявления о том, что они продолжат концертный тур под именем Gorgoroth и что именно Гаал и Кинг были «движущей силой Gorgoroth в последние восемь лет». Через два дня было опубликовано ещё одно заявление Гаала. В нём говорилось, что «Gorgoroth не распались, а продолжают существовать в новом виде». Инфернус со своей стороны заявил, что претендует на имя Gorgoroth, как единственный участник группы, остававшийся в ней со дня основания.

Практически одновременно с публикацией этих заявлений Гаал и Кинг объявили имена музыкантов, с которыми они планировали отправиться в турне: гитарист Телох (Teloch, Мортен Иверсен) и Николас Баркер (бывший ударник Cradle of Filth и Dimmu Borgir). В качестве постоянного студийного ударника был заявлен Хеллхаммер.