Dopo lo storico split dai Sepultura, il loro leader Max Cavalera (mente che stava dietro quasi completamente da solo agli ultimi tre dischi della band) collabora dapprima con i Deftones, scrivendo e cantando per loro il pezzo Headup (dedicata al suo figliastro Dana Wells, la cui morte è alla base dello split), poi fonda una nuova band. Il nome del gruppo, Soulfly, proviene proprio dal testo di Headup.

Sull'omonimo disco di debutto, Cavalera si propone di spingere all'estremo lo sperimentalismo sonoro già adottato in Roots, aumentando enormemente il grooving dei riff di chitarra e la componente tribale: non solo le percussioni dominano l'album, ma perfino i componenti del gruppo sono turnisti provenienti da altre band che Cavalera cambia continuamente, perché vede la band come una tribù, una famiglia.
Questa componente spirituale va di pari passo all'adozione di una piega ancora più crossover-numetal del songwriting di Max, che difatti trova la produzione ideale nel tocco di Ross Robinson.
Il disco è inoltre infarcito di guest, soluzione derivante dagli album hip-hop.
Tra i pezzi spiccano la furibonda opener Eye for an Eye, le micidiali No Hope = No Fear e Bumbklatt (entrambe dal drumming travolgente), la violenta e drammatica Bleed (che si avvale di DJ Lethal e Fred Durst dei Limp Bizkit come guest), la primordiale e con afumature industrial Tribe, la strumentale e soffusa Soulfly, la melodica e catchy Umbabarauma (che diventa un po' l'inno ufficioso del Brasile ai mondiali di calcio del 1998), la trascinante Quilombo.
Max inoltre raggiunge anche vette di religiosità (First Commandment, con Chino Moreno dei Deftones come guest-vocalist), nu-metal (Fire e No), estremismo sonoro (The Song Remains Insane), e sublima il tutto nel colossale manifesto di Prejudice.
Si tratta di un disco che spruzza anarchia e voglia di abbattere gli schemi da ogni poro.

dei Soulfly di Max Cavalera, Primitive è il naturale proseguimento del disco di debutto: raggruppa tutti gli elementi più incisivi e caratteristici del precedente lavoro, e li spinge in una dimensione più matura, compatta e d'impatto.
Primitive è per i Soulfly l'equivalente di quello che sarà Toxicity per i System of a Down, per fare il paragone con una band dal sound per certi versi affine.
L'album si apre alla perfezione con il pezzo più riuscito in tutta la carriera della band: Back to the Primitive, dall'introduzione che dura precisamente un minuto prima dell'esplosione, è un compendio devastante e pressoché perfetto di nu-metal e tribalismi, e le sue liriche sono uno degli anthem più minimali e convincenti mai scritti da Cavalera ("Back to the primitive, fuck all your politics, we got our life to live the way we want to be" ... "Back to the primitive, fuck all your politics, forever we will be what we want to be").
Pain pecca nell'essere costruita su praticamente un solo riff, e quindi risulta ripetitiva; fortunatamente come ospiti al microfono ci sono Avenell dei Will Haven e Moreno dei Deftones, che sollevano notevolmente il pezzo intrecciandosi alla voce di Cavalera.
Tutto torna sui binari giusti con Bring It, che combina il lato più hardcore e diretto dei Sepultura ad una divagazione reggae imprevedibile, e Jumpdafuckup, in cui Corey Taylor degli Slipknot fonde i suoi growl a quelli di Cavalera, con un risultato impressionante.
Pezzi come Boom, Mulambo e Terrorist (quest'ultima con al microfono anche Tom Araya degli Slayer, segno della riappacificazione tra i due cantanti) aggiornano il nu-metal fondendolo sia con tribalismi sia con una vena estrema (riflettente le radici sonore di Cavalera) che suona molto più genuina e potente di quella di dischi che usciranno negli anni seguenti da parte di band come Slipknot o DevilDriver.
In Memory of... porta la formula nel genere hip-hop (anche se non raggiunge i livelli che avrebbe potuto, risultando ripetitiva), mentre la sperimentale Son Song, che unisce melodie pop in tempo dispari ad escursioni heavy-rock, vede un duetto inimmaginabile (quello tra Cavalera e Sean Lennon, figlio del più celebre John).
I momenti soffusi continuano con il prog-jazz etnico di Soulfly II, mentre la finale Flyhigh, altro anthem, sfodera un potente riffing groove-metal su cui si amalgama alla perfezione con la voce soul della cantante Asha Rabouin.
Tutti i pezzi sono inoltre spezzati quasi sempre da bridge, "girotondi" e divagazioni che anticipano le esplosioni chitarristiche, soluzione che porta all'estremo uno degli stilemi del nu-metal, facendo sì che tale elemento dopo questo album diventi un semplice cliché del genere.
L'unico difetto del lavoro sono le troppe collaborazioni: alcune valorizzano notevolmente l'album, altre invece spersonalizzano il sound della band e dunque spezzano il flusso di creatività e potenza del disco.

Terzo episodio dei Soulfly, popolarmente chiamato 3 (anche se in realtà il vero titolo è un simbolo grafico comune a molte religioni, nonché il mantra più sacro della religione induista, traslitterato come Aum o Ohm, che graficamente somiglia al numero arabo 3).
Semplicemente una versione non ispirata dei due precedenti album, 3 vede Cavalera, nell'epoca della decadenza del trend nu-metal, semplificare estremamente il proprio songwriting già non troppo complicato (probabilmente sia per mancanza di idee sia per un fattore di mercato), confezionando un prodotto piatto e più orecchiabile.
Downstroy è un auto-plagio di Eye for an Eye, Seek 'n' Strike è tanto groovy ed esplosiva al primo ascolto quanto radio-friendly e ripetitiva già al secondo, Enterfaith ha un sound potente ma è costruita su parti chitarristiche banali, One vede la collaborazione vocale di Christian Machado degli Ill Niño e risulta essere uno dei pezzi più riusciti, grazie soprattutto alle improvvise esplosioni e al tappeto di percussioni, L.O.T.M. recupera malamente il thrash-metal dei primi Sepultura.
Le idee scarseggiano notevolmente anche nella seconda metà dell'album: 9-11-01 è un inutile minuto di silenzio dedicato agli attentati dell'11 settembre 2001, Call to Arms un non troppo brillante thrash-metal con sfumature groove dedicato alle vittime di quegli stessi attentati, One Nation e Sangue De Bairro sono due cover.
Soulfly III è uno degli episodi migliori, ma non è all'altezza delle due strumentali sui dischi precedenti.
Brasil (affogata nelle percussioni tribali e guidata da un basso groovy che compensa in parte le liriche ridondanti e auto-plagiate) e la lunga Tree of Pain (8 minuti, con rap del figlio Ritchie Cavalera e vocalizzi soul di Asha Rabouin) pretendono di essere anthem, ma convincono appena parzialmente.
In compenso, una collaborazione con il fratello Igor segna la riappacificazione (dopo quasi 8 anni) tra i due musicisti.
La conclusiva Zumbi è uno strumentale folk-etnico.

Dopo un nuovo cambio di line-up (con musicisti provenienti da band come Primer 55, Megadeth, Ill Niño), esce un nuovo disco per i Soulfly di Max Cavalera.
Prophecy abbandona i principali stilemi nu-metal (di pari passo con la decadenza del trend) in favore di un approccio chitarristico più vicino al groove-metal, una forte influenza dalla world-music (dovuta ad un viaggio in Serbia di Max), e un'impronta ancora più religiosamente cristiana ai suoi testi.
Il progetto, sulla carta, è ottimo. In pratica, però, annega troppo spesso a causa di un songwriting zoppicante.
Poche, ma buone, le sorprese: la potenti, curate e trascinanti title-track e Living Sacrifice (quest'ultima portata da parti chitarristiche devastanti ad essere uno dei massimi vertici di sempre della band), la strumentale Soulfly IV, il conclusivo soul con tocchi etnici e coda da banda di paese Wings.
Il resto si divide tra ripetizioni estenuanti del metal dei precedenti album, solo più influenzato dal death-thrash (Defeat U, Born Again Anarchist, Execution Style, Porrada), ed esperimenti di fusioni musicali (Mars, che parte death-thrash e termina reggae-folk, e Moses, con trombe e ritmi reggae) che disperdono il nucleo dei pezzi rendendo il risultato finale eccessivamente disomogeneo.
Non è un disco di difficile ascolto, come ha scritto qualcuno (a meno che non si riferisse ad un pubblico di metalheads), è semplicemente un disco dispersivo (nelle tracce più "crossover") e poco ispirato (nelle tracce più metal).
A livello di testi, Max a tratti diventa irritante con il suo "integralismo" cristiano (leggere le liriche di I Believe per un esempio), ma poi si fa perdonare raggiungendo alti livelli di spiritualità (come in Moses, dedicata al suo ultimo figlio).
La singer di impronta soul Asha Rabouin, ormai quasi una componente del gruppo, canta su I Believe e Wings.
In generale, sebbene più superficiale e ripetitivo rispetto ai primi due dischi, l'album è comunque più conciso e scorrevole del precedente 3, rispetto al quale suona dunque come un lievissimo passo in avanti.
In the Meantime è una cover degli Helmet.

Il 2004 vede purtroppo un episodio drammatico: Moses, ultimo figlio di Max Cavalera, perde la vita a soli 8 mesi.
Inutile dire che l'avvenimento influisce pesantemente sul musicista, il quale però decide di proseguire ugualmente con il suo progetto Soulfly. Stavolta viaggia tra Serbia, Turchia, Russia, USA e Francia per cercare nuove influenze e nuove risposte.
Dark Ages esce nel 2005, e si presenta indubbiamente come il miglior album dei Soulfly (secondo solo a Primitive).
Max abbandona l'impasto sonoro costruito sul crossover-rock noisy tipico dei precedenti full-length: raccoglie le principali caratteristiche del suo sound e le innesta in un lavoro in cui riffing e drumming arrivano dritti dal death-thrash del suo gruppo originario, i Sepultura (quelli di Chaos A.D., particolarmente), recuperando e aggiornando pienamente lo spirito infuriato originale di quel periodo.
Non si può più parlare di nu-metal o crossover-rock; Dark Ages conia un metal molto vario ma che prende le sue principali caratteristiche dal groove-metal e dall'estremismo sonoro tipico del death-metal, colorato grazie a una rinnovata ispirazione artistica.
Carved Inside sbuca dritta dai Sepultura dei primi 1990s in una formula brillantemente aggiornata grazie agli innesti hardcore-punk, Arise Again è uno dei pezzi più trascinanti mai scritti da Max, Molotov è hardcore-punk portato all'estremo, Frontlines (che nel testo cita Disposable Heroes dei Metallica) e Fuel the Hate sono death-metal vitalizzati da cambi ritmici ed esplosioni chitarristiche.
Riotstarter mescola eccellentemente distorsioni chitarristiche, percussioni ed industrial-metal.
Bleak è groove-metal estremamente aggressivo contaminato dall'industrial, come non se ne sentiva dai tempi d'oro dei Fear Factory.
(The) March è un breve intermezzo, sempre macchiato da sfumature "industrial", e gli 8 minuti di Staystrong presenta una ben riuscita unione tra groove-metal, death-thrash e inquiete parentesi melodiche.
La chiusura, affidata alla nuova strumentale Soulfly V (11 minuti), non delude, ed è anzi tra le migliori tracce strumentali mai scritte dalla band.
Gli elementi etnici sono ancora presenti, ad esempio in I and I o in Innerspirit, ma non hanno più nulla della passione tipicamente brasiliana delle precedenti release: sembrano piuttosto provenire da una band metal scandinava.
Al tutto contribuiscono le atmosfere dei brani, rese ancora più inquietanti e "dark" dai vari campionamenti (vedesi la cupissima opener The Dark Ages) e dalle tastiere che fanno saltuariamente capolino allo scopo di rendere più opprimente il sound.

Nel 2008 debutta su disco il progetto Cavalera Conspiracy, con il quale i due fratelli Max e Igor Cavalera tornano a suonare nella stessa line-up dopo 12 anni di separazione.

Il sesto album dei Soulfly, Conquer (Roadrunner, 2008), è essenzialmente una versione molto più monotona, derivativa e stanca del buon precedente Dark Ages.
Purtroppo il momento di rinnovata ispirazione di Max sembra proprio terminato: ripulito il sound da quasi ogni sfumatura etnica, appiattiti e rimasti privi d'energia i pochi riff groove-metal, assente l'anima viscerale hardcore-punk, ridotti i pezzi a schematici e già sentiti thrash-metal, nelle tracce di Conquer è perfino assente l'atmosfera apocalittica che convogliava la genuina rabbia esistenziale di Dark Ages.
Timidi accenni synth-rock (Rough) o mediorientali (For Those About to Rot) a concludere le tracce, così come cambi ritmici non molto frequenti e comunque prevedibili, non sollevano di certo la qualità complessiva.
Si distinguono dalla massa solamente le finali Touching the Void (7 minuti infernalmente cadenzati tra doom, groove-metal e arrangiamenti etnici ma claustrofobici, grazie anche ai preziosi contributi di Fedayi Pacha) e la solita parentesi strumentale Soulfly VI (che comunque è nettamente inferiore alle precedenti, visto che stavolta sembra quasi una banale power-ballad hard-rock sbucata dai 1980s).
Non si capisce ormai il motivo di una separazione tra Soulfly e Cavalera Conspiracy: i primi sono ora diventati quasi identici ai secondi, sound ritrito e scialbo compreso.
Da segnalare le guest vocals di David Vincent (dei Morbid Angel) nell'opener Blood Fire War Hate, e di Dave Peters (dei Throwdown) in Unleash.

La formazione dei Soulfly resta la stessa di Conquer anche per il successivo settimo album Omen (Roadrunner, 2010).
Bloodbath & Beyond apre il fuoco con una scarica di hardcore misto a thrash-metal, mostrando una maggior tendenza a recuperare il "groove" perso con il disco precedente, ma le promesse non vengono mantenute lungo il corso del disco.
Rise of the Fallen non presenta parti di chitarra e drumming interessanti, ma viene vitalizzata da brevi tocchi percussivi ed elettronici, e soprattutto dal contributo vocale di Greg Puciato, che la avvicina al sound dei The Dillinger Escape Plan, così come il guest Tommy Victor dei Prong riesce a dare un senso e una propria impronta all'altrimenti non molto interessante groove-metal dalle cadenze marziali opprimenti di Lethal Injection, su cui tuttavia si innestano dei virtuosismi chitarristici in modo non troppo convincente; entrambe costituiscono, assieme all'opener e alla consueta strumentale Soulfly VII (soffusa ballad hard-rock con tocchi latini, orecchiabile anche se suona di vent'anni troppo vecchia), gli unici momenti godibili del disco.
Great Depression abbassa il livello generale con una trita fotocopia del thrash alla Slayer, e su coordinate altrettanto stanche e già sentite si muovono Kingdom, Jeffrey Dahmer e Mega-Doom; un più marcato spirito hardcore rende Counter Sabotage e Off With Their Heads leggermente superiori alle altre tracce, ma la stessa formula fa invece suonare Vulture Culture solo come una parodia del sound di Beneath the Remains dei Sepultura.
Sembra incredibile il modo in cui lo stesso autore di album continuamente traboccanti di variazioni stilistiche come Soulfly e Primitive si sia ora ridotto a scrivere dischi tanto monotoni e mentalmente chiusi come Conquer e Omen.