Второе воссоединение (2001–2004)

В 2001 году группа снова воссоединяется, чтобы выступить на Thrash of the Titans, благотворительном концерте, устроенном для сбора средств на лечение рака вокалиста Testament Чака Билли и Чака Шульдинера, лидера Death. На этот раз у группы есть четкая цель - выпустить новый студийный альбом, и Exodus

с Полом Бэйлоффом за микрофонной стойкой продолжает давать концерты у себя в Сан-Франциско и ближайших городах.

Однако, в феврале 2002 года происходит трагедия: Пол Бэйлофф переносит инсульт и умирает. Чтобы не сорвать концертные обязательства группа нанимает проверенного вокалиста - Стива "Зэтро" Сузу. Несмотря на смерть Бэйлоффа, Гэри Холт полон решимости записать новый альбом. Результатом явился выход в 2004 году Tempo of the Damned под эгидой немецкой Nuclear Blast Records. Работа была посвящена памяти Пола Бэйлоффа и вышла ровно во вторую годовщину его смерти — 2 февраля 2004 года. Это настоящий подарок поклонникам старой классики группы — Bonded by Blood, Pleasures of the Flesh и Fabulous Disaster. Но в то же время «Blacklist», «War is my Sheppard», «Shroud of Urine» станут настоящим наглядным уроком для молодого поколения трэшеров. Во время записи альбома произошла странная вещь: на альбоме должен был присутствовать трек "Crime of the Century", однако его запись исчезла при таинственных обстоятельствах. Песня рассказывала о временах, когда Exodus сотрудничала с Century Media (дочерней компанией которой являлась Nuclear Blast Records). Несмотря на то, что компания публично отрицала факт вмешательства, ходили слухи, что Century Media вынудили группу исключить песню из альбома. Её место в альбоме заняла песня "Impaler", написанная еще в соавторстве с Кирком Хэмметтом, но впервые записанной в студии. Также этот трек присутствует на концертном альбоме Another Lesson In Violence. Возвращение группы состоялось на всех фронтах — Exodus возглавил осенний тур Bonded by Metal over Europe. Также был выпущен лимитированный сингл War is my Sheppard, который продавался только в ходе упомянутого тура и через почтовую рассылку Nuclear Blast. Помимо этого для композиции «War Is My Shepherd» было снято видео. Второе видео — для композиции «Throwing Down».

Эра Роба Дьюкса (с 2005 по настоящее время)

В 2005 году Рик Ханолт решает покинуть состав группы и сосредоточиться на семейной жизни. Его заменяет бывший гитарист Heathen Ли Элтус. Том Хантинг также заявляет о своем уходе в связи с вновь проявившимися проблемами со здоровьем, заставившими его уйти из группы в прошлый раз. Место за ударными занимает Пол Бостаф (в прошлом отыгравшим с Forbidden, Testament и Slayer). Стив Суза вновь покидает группу по причине финансовых разногласий с группой. Первое время его заменяет Стив Эскуивэл (ex-Defiance, Skinlab). В конце концов группа находит постоянного вокалиста в лице Роба Дьюкса.

Обновлённым на 60% составом группа в 2005 году выпускает Shovel Headed Kill Machine. Тур в поддержку пластинки включал США, Европу, Японию, а также Австралию, где прежде группа еще не выступала.

В марте 2007 года Том Хантинг снова возвращается в группу, и за этим последует запись очередной пластинки, получившей название The Atrocity Exhibition... Exhibit A. Летом 2008 года Exodus выступают на фестивале Wacken Open Air в Германии, а в апреле 2009 участвуют в совместном североамериканском туре с Kreator.

Кроме того, осенью 2008 года Exodus полностью перезаписывают дебютный Bonded by Blood и выпускают его под названием Let There Be Blood. Гэри Холт сделал официальное заявление по поводу решения группы перезаписать Bonded by Blood:" После многих лет планирования и дискуссий мы, наконец, закончили перезапись "Bonded by Blood". Мы решили назвать это "Let There Be Blood", таким образом мы хотим отдать дань уважения Полу Бэйлоффу и показать насколько актуальными являются эти песни сейчас, которые мы с ним сочинили тогда. Мы не хотим заменить оригинал, это невозможно. Мы просто отдаём эти песни в пользу современного искусства. Это то, о чём мы говорили до смерти Пола, и это всегда было важно для нас. Мы были очень рады войти в студию, чтобы снова записать эту классику, и сейчас мы возвращаемся, чтобы сделать следующую студийную запись!"