O pouco de publicar [[Waking the Fallen]], a banda comeza a gravar o álbum [[City of Evil]] coa grande discográfica Warner Bros records. Con este conseguiron grandes ventasvendas, e comeza unha nova etapa tamén no estilo musical, xa que deciden afastarse un pouco do estilo metalcore que os precedía. Nun principio asociábase o cambio musical aos danos nas cordas vocais que sufrira o vocalista [[M. Shadows]] e lle levaran ó quirofano, mais no DVD [[All Excess]] el mesmo aclara que non tivo que ver. Meses antes do lanzamento de [[City of Evil]], [[M. Shadows]] estivo mellorando as súas cualidades vocais co adestrador Ron Anderson, coñecido por traballar anteriormente con artistas como [[Axl Rose]],[[Kylie Minogue]] ou [[Chris Cornell]]. O primeiro single deste álbum foi “Bat Country”, o título desta canción proven do libro "Fear and Loathing in Las Vegas" do escritor Hunter S. Thompson onde Raoul Duke di: “Non podemos parar aquí. Este é un pobo morcego”. Os seguintes singles foron "Beast and the Harlot"(o seu riff ocupa o 10º posto según a revista Total Guitar como mellor riff do século 21), "Seize the day" e tamén gravaron un video en vivo para a canción "Burn it down". Antes de sacar o seu seguinte álbum en xullo de 2007 sae o DVD [[All Excess]] que inclúe actuacións en vivo, videos musicais, imaxes do backstage e documental sobre as vivencias da banda desde os seus comezos en 1999.
=== Avenged Sevenfold e Diamonds in the Rough(2007-2008) ===
