2000-2008 thumb|left|James McIlroy podczas koncertu 7 grudnia 2012 roku W 2000 roku w odnowionym składzie w Parkgate Studios zespół przystąpił do prac nad kolejnym wydawnictwem pt. Midian. Tematycznie nawiązywało ono do biblijnych Midianitów, potomków Abrahama oraz jego ostatniej żony Ketury. Okładkę płyty przygotował plastyk J.K. Potter. Album ukazał się 31 października 2000. Teksty na płycie zostały zainspirowane twórczością takich pisarzy jak Clive Barker czy H.P. Lovecraft. Ponadto muzyka na wydawnictwie charakteryzowała się łagodniejszym brzmieniem w stosunku do poprzednich wydawnictw zespołu.
Ostatnie wydawnictwo grupy w znacznym stopniu odbiegało od stylistyki blackmetalowej, zawierało połączenie muzyki gothic- oraz heavymetalowej, słyszalne było to szczególnie w partiach solowych gitary prowadzącej. Również sam zespół w komentarzach wyraźnie odciął się od stylistyki wypracowanej na poprzednich albumach. Gitarzysta grupy Paul Allender w związku z głosami krytyki stwierdził: „Nie uważam nas za zespół blackmetalowy, ale raczej za ekstremalny zespół metalowy. Z mojego punktu widzenia ludzie uważają nas za blackową grupę ze względu na to jak się ubieramy.