Przed nagraniem Shovel Headed Kill Machine zespół opuszcza trzech członków. Steve Souza został usunięty z zespołu, natomiast Rick Hunolt i Tom Hunting odeszli podając jako powody chęć poświęcenia się rodzinie oraz problemy ze zdrowiem. Płyta ostatecznie została nagrana w składzie uzupełnionym o gitarzystę Lee Altusa występującego wcześniej w Heathen, perkusistę Paula Bostapha oraz Roba Dukesa, byłego technicznego zespołu, który objął pozycję wokalisty.
W marcu 2007 zespół ogłosił powrót do składu Toma Huntinga. Z Exodusem w przyjacielskiej atmosferze pożegnał się Bostaph.
W czerwcu 2014 zespół ogłosił rozstanie z wokalistą Robem Dukesem i powrót poprzedniego wokalisty Steve’a „Zetro” Souzy.
Dyskografia thumb|200px|Gary Holt podczas koncertu 10 października 2009 thumb|200px|Gary Holt podczas koncertu 27 października 2005 thumb|200px|Lee Altus i Rob Dukes podczas koncertu 27 października 2005 thumb|200px|Rob Dukes, Jack Gibson i Gary Holt podczas koncertu 27 października 2005
Albumy studyjne Rok Tytuł Pozycja na liście Sprzedaż USA USA Ind.