biorąc udział w europejskiej trasie z Cannibal Corpse.
W lipcu 1998 roku w Millbrook Sound Studios, z pomocą producenta Paula Orofino, zespół rozpoczął nagrywanie trzeciego albumu – Failures for Gods, który miał premierę rok później – 1 czerwca 1999 roku.
W roku 2000 Immolation wzięło udział w trasie z Six Feet Under, a 7 listopada tego roku ukazał się czwarty album – Close to a World Below.
W roku 2001 z Immolation odszedł Thomas Wilkinson, którego – do czasu przyjęcia Billa Taylora z Angelcorpse – zastępował John McEntee z Incantation. W maju zespół wziął udział w europejskiej trasie z Deranged, Deströyer 666, Decapitated i Soul Demise, a we wrześniu zakończył współpracę z wytwórnią Metal Blade.
W czerwcu 2002 roku grupa podpisała kontrakt z Listenable i 28 października ukazał się album Unholy Cult, podobnie jak Close to the World Below, wyprodukowany przez Paula Orofino. Promując Unholy Cult, zespół dużo koncertował: w grudniu 2002 roku wziął udział w europejskiej trasie No Mercy X-Mass Festivals m.in. z grupami Six Feet Under, Marduk, Kataklysm, Exodus; w marcu i kwietniu 2003 roku – w europejskiej trasie z Cradle of Filth;