La definitiva maturità per il neonato progetto Soulfly giunge con Primitive, concreta personalizzazione stilistica della formazione sudamericana che con il suo ibrido di nu metal e groovy thrash metal misto a sonorità etnico-tribali ha ormai ottenuto una certa notorietà nel panorama metal. Molti vecchi aficionados dei Sepultura in realtà continuano a guardare con sospetto la svolta stilistica di Max Cavalera, vista come un “tradimento commerciale” ed un “ripudio” delle sonorità classiche dei brasiliani per seguire la moda del momento, ma come già accennato i Soulfly reinterpretano alla loro maniera le loro influenze, realizzando così quello che viene ancora oggi soprannominato “tribal metal”, e le condiscono con potenza, impatto e carica di altissimo livello.
Ancora una volta molte guest stars (nella recensione segnaliamo le più rilevanti, per la lista completa vedere la line-up), che arricchiscono la proposta del disco, seppur diano la sensazione che se si fosse esagerato si sarebbe andati incontro al procedimento inverso, cioè uno snaturamento del gruppo a causa della spersonalizzazione della propria musica. Inoltre, cambio di line-up. Max spiegò sul suo sito questo fatto:

"This is an approach that I've wanted to do for a while. I never wanted Soulfly to be a band like Metallica, with the same four guys. On every Soulfly album, we've changed the line up and it will probably continue that way. In order to do that, I had to start from the inside out and bring in people who caught my attention, that I had never played with before, and create this."

Nuovamente, i Soulfly esemplificano di un disagio carico di dubbi e di rabbia verso un mondo carico di contraddizioni, di ipocrisie e di spregevolezza. Per fronteggiare un futuro pessimistico e spietato, l’unico motivo è quindi ritrovare la propria essenza facendo ritorno alle proprie origini, alle proprie radici (Roots), una riscoperta della propria primitività, e i Soulfly, non un gruppo, ma una “grande famiglia e tribù” (come Max lo chiama), si fanno portavoce di questo messaggio. I testi presentano frasi fortemente d’impatto e comunicative, seppur di una banalità disarmante.

Di questi testi ne è un immediato esempio il primo brano, Back of the Primitive, che recita: "back to the primitive, fuck all you politics, we got our life to live the way we want to be; back to the primitive, fuck all you wannabes, forever we will be, what we want to be". Il confine fra l’efficace e significativo messaggio attuale e il semplice slogan per chi si lascia suggestionare molto, troppo facilmente è molto sottile in questo caso. L'intensità e l'impatto sono comunque a livelli altissimi, sembra che l'energia di Soulfly non si sia dispersa, anzi, si stia ancora sprigionando, come se il grosso dovesse ancora vedersi. Nu metal veloce e ostinato, incalzante al massimo, il ricordo dei Korn c'è, ma è come se fossero nati nella giungla sudamericana e fossero stati completamente contaminati, nell'anima, dall'impeto selvaggio della Tribù. Come se la rabbia di una generazione trovasse nella propria essenza più naturale l'energia per venire buttata fuori e urlata al mondo. Pain vede l'intervento di Chino Moreno dei Deftones che esalta la componente moderna della canzone e la tinge di tonalità più oscure, soprattutto l'intermezzo angosciante verso la fine. Le urla sguaiate richiamano fortemente il senso di rigetto verso il disagio generazionale espresso dalla scena alternativa americana, forse troppo, anche se non quanto gruppi come i Linkin Park che rubacchieranno abbastanza e banalizzeranno questi interventi. Bring It prosegue su di un thrash/nu metal ossessivo ed esasperato, furibondo, sembra quasi che siano tornati i Sepultura a suonare. Ma da metà canzone ci si assesta su sonorità più pacate, senza schitarrate e con solamente brevissimi interventi di chitarra ora quasi reggae, ora più vicini al crossover, accompagnati dalla batteria che scandisce la canzone con la sua regolarità tagliente. L'atmosfera rimane in ogni caso inquietante, fino all'esplosione finale. Jumpdafuckup è scritta in collaborazione con Corey Taylor degli Slipknot, e il suo zampino è immediatamente riconoscibile nel testo frustrato e pieno di rancore (con la sua caratteristica auto-indulgenza che più che angosciare lascia perplessi e dubbiosi…). E anche le vocals si ricollegano a quelle del gruppo di Des Moines, quelle pulite e malinconiche di Corey che rapidamente si tramutano in un simil-rap irato e poi lasciano spazio alla voce dura e tenace di Cavalera. Mulambo ripiega sul lato più acido e ossessivo dello stile dei Soulfly, tingendolo di richiami al folklore brasiliano e a personaggi storici dell'America latina che Cavalera definisce "rivoluzionari" e rispetto ai quali si è "come loro". Le percussioni tribali sono fra le più intense del disco, contorno squisito e al tempo stesso rabbrividente a questa intensa esplosione selvaggia. Son Song vede ospite questa volta Sean Lennon (figlio dell'arcinoto John). Il nu metal è meno incalzante e più groovy, i riff hanno ritmiche travolgenti, il finale è anche calmo, lasciato alla sola sezione ritmica accompagnata da poche tenui e dolci note che alla fine rimangono da sole (tranne per il vero epilogo che ritorna al giro acustico iniziale di Back to the Primitive); la voce suadente di Sean sembra quasi stonare con l'ugola ruvida e piena di rabbia di Max ma alla fine genera un contrasto abbastanza curioso e interessante. Boom è uno dei pezzi più divertenti del disco, davvero grintosa e dal piglio trascinante, soprattutto il chorus si potrebbe considerare molto accattivante nella sua semplicità. Terrorist è scritta in collaborazione con Tom Araya degli Slayer, ed infatti è uno dei pezzi più thrash metal dell'album, forse più nella seconda parte della canzone che si avvicina maggiormente alle sonorità estreme che la prima, ancora in piena ottica nu/groove.

The Prophet è un brano breve e scarno ma fortemente d’impatto, soprattutto nel finale dove le percussioni tribali prendono le redini del brano e catturano l’ascoltatore; intensa, dinamica canzone fortemente accattivante, la sua brevità catalizza tutte queste caratteristiche, per fare una metafora con citazione (da Kurt Cobain), è come se bruciasse rapidamente piuttosto che "spegnersi lentamente" (si fa per dire, perché i Soulfly sono tutto un fuoco dall'inizio alla fine, tranne nei momenti d'intermezzo più tranquilli). Il suo potenziale live garantisce molti salti e divertimento. Soufly II è la continuazione della titletrack già presente nell’omonimo debutto, una piacevole ed esotica strumentale che si lascia gustare appieno in tutta la sua interezza. E' il lato più tradizionale e meditato del gruppo, accanto a quello più furioso in un rapporto complementare in perfetta simbiosi. In Memory of… (scritta in collaborazione con i Cutthroat Logic) è un hip hop oscuro e rabbioso, soprattutto nel chorus dove Max urla le ennesime parole di grande effetto (e scontatezza). Come schema la canzone ricorda un po’ Children of the Korn della band di Davis & soci, ma si sviluppa verso altre strade, soprattutto nell’effettistica ridotta al minimo in favore dell’elemento acustico, di una sezione ritmica serrata e di un’atmosfera “da tribù di strada” suggestiva. E' però forse un po' troppo ripetitiva, accorciandola di poco sarebbe potuta essere ancora più efficace, ma anche così rimane decisa e accattivante. Chiusura affidata a Fly High, dal piglio roccioso ed orecchiabile e che vede l'intervento alla voce della cantante Asha Rabouin. La sua voce, profonda e sensuale, caratterizza in maniera davvero interessante questa canzone nel chorus, accompagnata dall'organetto che davvero, in altre occasioni avrebbe stonato, ma che qui si sposa alla perfezione con le vocals carismatiche e piene di vitalità, valorizzandole e facendosi valorizzare. In questo caso i testi si allontanano di più dalla rabbia consueta del gruppo, sono più carichi di speranza e di sogno, e anche di elementi cristiani (proprio il chorus sintetizza tutto ciò: "just let my soul fly free and let me be the one God wants me to be").

Primitive è il disco della consacrazione per i Soulfly, oltre che del trionfo commerciale in America, sui cui aleggiano però le critiche dei fan più intransigenti e il fattore "ospiti e turnisti": queste numerose guest stars sono, in definitiva, la croce e delizia del gruppo, perché, assieme al cambio di formazione, da un lato arricchiscono il disco e vi aggiungono molte influenze, dall'altro ormai iniziano ad essere troppo presenti e rischiano di spersonalizzare lo stile dei Soulfly. Una questione su cui Max pensò molto.