No dia 4 de outubro de 2005 o Exodus lançou o álbum Shovel Headed Kill Machine, não é o álbum favoritos dos fãs e nem um dos melhores se compararmos com anteriores e até mesmo posteriores, mas o álbum marcou por ser o primeiro após bruscas mudanças na formação do Exodus.
O Exodus nunca manteve uma formação sólida, desde a época de fita demos membros do Exodus foram entrando e saindo, mas a dupla Gary Holt e Rick Hunolt deixaram uma marca na banda, eles gravaram todos os 6 álbuns lançados pela banda, mas infelizmente isso teve um fim, no ano de 2004 Rick Hunolt deixou o Exodus para poder passar mais tempo com sua família, uma saída amigável. Mas essa não foi a única mudança no Exodus, o vocalista Steve “Zetro” Souza também deixou a banda, ele não era membro da formação original, mas gravou 5 de 6 álbuns da banda, a voz dele já estava registrada como a voz do Exodus, e por último Tom Hunting deixou a banda pela segunda vez.
Sobrando apenas o líder Gary Holt e baixista Jack Gibson, mas quem poderia substituir 3 membros que participaram da formação clássica e de álbuns como “Pleasure Of The Flesh” e “Fabulous Disaster”, bom, na bateria foi recrutado ninguém mais do que Paul Bostaph, que até então já tinha tocado nas bandas Slayer e Forbidden, na guitarra Lee Altus fundador da banda de Thrash Metal Heathen, os dois foram membros de bandas aclamadas do Thrash Metal.
Mas e o vocal, quem iria assumir a responsabilidade de substituir Zetro era provavelmente a maior preocupação, bom, diferente dos novos membros, o Exodus decidiu escolher um desconhecido, que até então nunca teve registro em nem uma banda clássica do Thrash Metal, o nome dele era Robert “Rob” Dukes, que tinha como característica facial uma cicatriz, que foi causada por uma garrafa de vidro quebrada após se envolver em uma briga enquanto estava bêbado.
Bom, para mostrar se essa formação daria certo ou não, foi lançado o álbum “Shovel Haded Kill Machine”, que, como já dito acima não foi um dos melhores trabalhos do Exodus, é um álbum sólido de Thrash Metal, mas serviu de estreia para novos membros, que foram bem recebidos, para Lee e Paul talvez não fizesse tanta diferença, eles já tinham um currículo invejável, mas para Dukes, talvez fosse tudo ou nada, e ele foi muito mais que aceito pelos fãs não só do Exodus mas de Metal em geral, de um dia para outro um desconhecido se tornou a nova voz dos Exodus, alguns arriscam até em dizer que ele foi o melhor da banda superando Paul Ballof e Zetro, outros não, mas uma coisa era certa, sua vida talvez não fosse mais a mesma depois desse álbum.
Um novo capitulo começou se iniciou para Dukes, que fez apresentações memoráveis com Exodus, registro do Wacken 2008 pode mostrar isso, e também trouxe um alivio para Exodus que conseguiu fazer uma excelente escolha para novo vocalista, e o álbum Shovel Haded Kill Machine foi o que marcou isso na história de ambos.
