Antichrist (1995–1996)Antes de que terminara el año 1994, Gorgoroth comenzó la grabación de su segundo álbum de estudio. Durante el proceso de grabación, que terminó en enero de 1996, la banda tuvo algunos cambios en su formación. Hat dejó el grupo en septiembre de 1995 y fue reemplazado por el vocalista de Obtained Enslavement Pest. Ambos cantantes participaron en el álbum, pues cada uno puso su voz en tres temas. Samoth también dejó Gorgoroth y fue sustituido, primero por Storm y luego por Ares, aunque ninguno contribuyó en el álbum; fue Infernus quien grabó las pistas de bajo. Frost, tras grabar las pistas de batería, abandonó el grupo y su puesto fue ocupado por Grim, compañero de Infernus en Borknagar.
Durante 1995, la banda solo realizó dos actuaciones en directo, en Bergen y en Londres como teloneros de Cradle of Filth y Primordial en el London Astoria. Este último fue el primer concierto de la banda con Pest y Ares. Ese año, Gorgoroth fue contratada por la discográfica alemana Malicious Records, con quienes publicaron Antichrist y la reedición de Pentagram. Tras terminar la grabación de Antichrist, Gorgoroth realizó su primera gira europea con Satyricon y Dissection en abril de 1996. Al finalizar la gira actuaron en Bergen con Hades Almighty y Gehenna, donde grabaron el EP en directo The Last Tormentor, reeditado en 2007 con el nombre Bergen 1996. Antichrist fue lanzado en junio con una portada similar a la de su antecesor pero con una cruz invertida en el centro y con el subtítulo True Norwegian Black Metal. La contraportada incluye la frase «The sin of Satan is the sign of Gorgoroth» («El pecado de Satán es el símbolo de Gorgoroth»)
Under The Sign of Hell (1997)Tras publicar Antichrist, Gorgoroth comenzó a grabar su tercer álbum de estudio, Under the Sign of Hell. Este fue el primer trabajo con Grim como batería y con Ares como bajista; aunque sólo en una canción, las demás fueran grabadas por Infernus. Grim dejó la banda tras la grabación del álbum y fue reemplazado por Vrolok. También llegó a la banda el guitarrista Tormentor. El álbum no se publicó hasta octubre de 1997, después de que Gorgoroth realizara una gira por Alemania y Holanda con Mystic Circle como teloneros. Durante la gira, la banda fue contratada por la discográfica alemana Nuclear Blast. Pest dejó la banda a finales de 1997 y su reemplazo fue el vocalista Gaahl.
Destroyer (1998)En mayo de 1998, fue publicado su primer trabajo con Nuclear Blast, Destroyer (Or About How To Philosophize With The Hammer), que incluye música grabada durante los últimos cuatro años. El álbum contiene la colaboración de varios músicos, siendo Infernus el único que participa en todos los temas. Destroyer incluye una versión del tema de Darkthrone «Slottet i det fjerne» interpretada por Infernus como vocalista y Tormentor como encargado de los instrumentos; y que fue incluida en el álbum tributo, Darkthrone Holy Darkthrone. Destroyer es el primer trabajo con el bajista T-Reaper (como vocalista en «The Devil, the Sinner and His Journey»), Gaahl (vocalista en «Destroyer») y Tormentor. Ivar Bjørnson de Enslaved fue el encargado del sintetizador en «The Devil, the Sinner and His Journey» usando el apodo Daimonion.
Antes de la publicación del álbum, Gorgoroth realizó una gira alemana con Cradle of Filth, Old Man's Child y Einherjer. En verano, actuaron en el Wacken, en el Tuska y en Oslo con Gehenna y Dødheimsgard.
Incipit Satan (1999–2001)En julio de 1999, Gorgoroth comenzó la grabación de su quinto álbum de estudio con los nuevos miembros King ov Hell y Sersjant Erichsen, bajista y batería respectivamente. En diciembre la banda realizó una gira europea junto a Morbid Angel y Krisiun. El álbum, llamado Incipit Satan, fue publicado en febrero del año 2000 y al igual que su antecesor cuenta con la colaboración de Ivar Bjørnson, además del cantante de rock Mikey Faust, que contribuye con voces limpias en la canción «When Love Rages Wild in My Heart». El batería Erichsen dejó el grupo tras la grabación del álbum y fue reemplazado por Kvitrafn. En mayo, Gorgoroth inició una gira europea como cabezas de cartel con Old Man's Child y Krisiun. En agosto actuaron en la primera edición del festival Hole in the Sky, realizado en homenaje a Grim, que había fallecido en octubre de 1999. A finales de 2001, Gorgoroth actúo por primera vez en América, concretamente en Estados Unidos, México y Colombia.
Twilight of the Idols (2002–2005)En 2002, Tormentor dejó el grupo debido a su mala relación con King ov Hell. En mayo, Infernus, King ov Hell y Kvitrafn comenzaron la grabación de su sexto álbum de estudio. Gaahl fue condenado a diez meses de prisión por torturar a un hombre, razón por la cual tuvieron que retrasar la grabación de su voz y no realizaron ninguna presentación en directo. Infernus, mientras tanto formó la banda Orcustus con Tormentor. Tras la liberación de Gaahl, terminaron la grabación del álbum, Twilight of the Idols (In Conspiracy with Satan), que fue publicado en junio de 2003. La portada del álbum fue censurada en algunos países por incluir una imagen de la iglesia de Fantoft quemada. Para las actuaciones en directo (aunque ese año sólo realizaron tres), la banda contrató como guitarrista rítmico a Apollyon de Aura Noir.
El 1 de febrero de 2004 Gorgoroth realizó una actuación en Cracovia, que fue publicada en DVD más tarde. El concierto generó una gran polémica y llegó a ser mencionado en todos los medios nacionales polacos debido a que la policía pretendía llevar a la banda a prisión por delitos religiosos y por crueldad animal. El escenario de la actuación fue cubierto con 100 litros de sangre de oveja, adornado con aproximadamente diez cabezas empaladas de ganado bovino; detrás de los miembros de la banda fueron colocadas cuatro personas desnudas crucificadas. Una de las mujeres se desmayó en la cruz y tuvo que ser atendida en una ambulancia. Sobre las acusaciones de tortura animal, los organizadores del concierto afirmaron que las cabezas de ganado habían sido compradas en una carnicería local. El resto del año promocionaron el álbum con varias actuaciones en distintos países; en marzo realizaron una gira sudamericana; en septiembre y octubre, con 1349 de teloneros, realizaron varias fechas en Europa y en noviembre hicieron una gira por Centroamérica. Kvitrafn dejó Gorgoroth para concentrarse en otros proyectos (Sahg y Jotunspor).
En 2005, la banda realizó una de sus giras más extensas, nuevamente con 1349 y visitando varios países europeos e incluyeron cinco fechas en España. El guitarrista rítmico de esta gira fue Skagg, compañero de Gaahl en el proyecto Gaahlskagg. Ese año también comenzaron la grabación de un nuevo álbum de estudio con la colaboración de Frost como batería.
Ad Majorem Sathanas Gloriam (2006–2007)En marzo de 2006 la banda terminó la grabación del álbum, después de que Gaahl pusiera voz a las pistas. Un mes más tarde el vocalista fue de nuevo encarcelado por torturar a un hombre. Infernus también entró en prisión por colaborar en la violación de una mujer.
Gorgoroth publicó Ad Majorem Sathanas Gloriam en verano de 2006 a través de la discográfica Regain Records. Poco tiempo después del lanzamiento del álbum, King abandonó la banda. De acuerdo con la página web de Gorgoroth, el bajista se marchó porque «tenía problemas para compaginar su trabajo en una banda satánica con su trabajo como profesor de primaria». Ad Majorem Sathanas Gloriam fue nominado en la categoría de mejor álbum de metal en la 35ª edición de los premios Spellemann. Gaahl fue puesto en libertad en diciembre e Infernus en enero del año siguiente.
En enero de 2007, Gaahl fue investigado por la policía noruega por sus comentarios en una entrevista para Metal: A Headbanger's Journey, donde dijo: «la quema de iglesias es algo que apoyo al cien por cien, que se debería haber hecho más y se hará mucho más en el futuro». En mayo, con King ov Hell de nuevo en la banda, realizaron la grabación del videoclip para la canción «Carving a Giant».
En julio y agosto, Gorgoroth volvió a actuar en directo a partir de diciembre de 2005, concretamente en Noruega, República Checa y Alemania. Después de estos tres conciertos, la banda realizó su última gira con Gaahl y King, en Sudamérica y con Belphegor como teloneros.