В сентябре 2003 года, после окончания тура, Долинг, Диас и Майорга покинули Soulfly, оставив Кавалеру единственным её участником.

Prophecy (2003)

В октябре 2003 Кавалера собрал новый состав Soulfly. Джои Нуньез вернулся на ударные, новым гитаристом стал Марк Риццо, бывший участник Ill Nino. В записи участвовало одновременно два басиста — Дэвид Эллефсон, экс участник Megadeth, и Бобби Бёрнс из Primer 55. Таким образом Макс попытался совместить старую и новую школы метала на альбоме.

Макс Кавалера объяснил на вебсайте группы, что хочет играть с разными музыкантами на каждом альбоме:

Так я собираюсь делать и дальше. Я никогда не хотел чтобы Soulfly была такой группой как Metallica, состоящая из тех самых четырёх парней. С каждым новым альбомом Soulfly мы меняли состав и скорее всего будем и дальше так продолжать

Часть альбома была записана в Сербии, с местными музыкантами из Eyesburn (трек «Moses»). Денни Марианино и Аша Рабуин (Asha Rabouin) также участвовали в записи, как приглашенные вокалисты. Продюсировал альбом сам Кавалера.

Prophecy был издан 30 марта 2004 года и в апреле того же года достиг 82 позиции в чарте Billboard 200 и вершины топ 50 Австралийских чартов. Очередной мировой концертный тур проходил при участии групп Black Sabbath, Ill Nino и Morbid Angel.

В феврале 2005 года, Soulfly издали свой первый DVD, названный The Song Remains Insane. Это был биографический взгляд на группу, который содержал концертные выступления коллектива по всему миру, интервью и все видеоклипы группы на то время. В августе 2005 года Roadrunner Records переиздали первый одноименный альбом группы в честь празднования 25-летия лейбла.

Dark Ages (2004—2007)

В декабре 2004 года началась запись пятого альбома Soulfly — Dark Ages.

Тогда же произошли трагические события с близкими Кавалеры: 8 декабря во время концерта в Коламбусе, штат Огайо, был застрелен близкий друг Макса, гитарист группы Pantera Даррел Эббот (Darrell «Dimebag» Abbott). 10 декабря скончался 8-месячный внук Макса и Глории Мозес.

В процессе записи Dark Ages Кавалера посетил Сербию, Турцию, Россию, Францию и США, где записывал различные треки вместе с местными музыкантами.

Основной состав Soulfly периода Dark Ages: Кавалера, Риззо, Нуньез, Бернс. Также участвовали Дэвид Эллефсон, вокалист группы Eyesburn Койот (Coyote), Билли Милано (Stormtroopers Of Death), Павел «Паштет» Филиппенко (FAQ), Ричи Кавалера (Incite). 4 октября 2005 года состоялся релиз альбома. Многие критики назвали Dark Ages возвращением Макса Кавалеры к thrash metal корням ранних дней Sepultura. Последовавший концертный тур проходил, по традиции, с помощью различных групп (Deftones, Korn, Throwdown, Skindred). Soulfly посетили Северную и Южную Америку, Европу, Россию и Австралию.

17 августа 2006 года Soulfly отыграли на 10th Annual D-Low Memorial show. Впервые со времен ухода Макса из Sepultura, на одной сцене с ним выступил его брат — Игорь Кавалера. Братья исполнили один из главных хитов Sepultura — «Roots Bloody Roots», а также «Attitude».

После окончания концертов в поддержку Dark Ages, члены группы сосредоточились на сторонних проектах.

Кавалера, вместе с Мэтом Таком (Matt Tuck), вокалистом Bullet For My Valentine, участвовал в записи сингла группы Apocalyptica «Repressed», в январе 2007 года посетил Россию, где отметился на альбоме московской группы FAQ, отыграл в Сербии совместно с System Of A Down. Марк Риззо со своим проектом в стиле фламенко-метал (flamenco-meets-shred metal) путешествовал по Северной Америке. Бобби Бернс приобрел студию в Орландо и также работал над сольными проектами (Love Said No, King Street).