Idući album novog materijala nakon The Gatheringa prvi je put spomenut 2002.[1] i izvorno je trebao biti objavljen početkom 2004.,[2] no nije bio dovršen do tog vremena. Zbog rasporeda koncerata i promjena u postavi objava uratka odgađana je godinama, a konačno je dovršen između 2007. i 2008.
Testament je prvi put spomenuo da radi na novom albumu u svibnju 2002.; komentirao je da gitarist Eric Peterson marljivo sklada nove pjesme za uradak i da će raditi na njemu "još neko vrijeme" jer je The Gathering "uradak koji je teško nadmašiti".[1] Također je potvrđeno da će biti "brutalan" i da će sadržavati "mnogo dvostrukih solističkih dionica gitarista Petersona i [tadašnjeg gitarista] Stevea Smytha."
Dana 15. veljače 2004. objavljeno je da će se grupi pridružiti Paul Bostaph, bivši bubnjar skupina Forbidden i Slayer, i da će snimiti album s ostalim članovima.[3] Također je najavljeno da grupa planira ući u studio u travnju ili srpnju i da namjerava objaviti uradak krajem 2004.