Après la mort de son beau-fils Dana, et le split de Sepultura fin 1996, Max Cavalera décide de monter son projet solo, une espèce de super groupe faisant la part belle aux guests stars. Soulfly est créé officiellement le 21 janvier 1998, lors d’un direct avec les Deftones à Nulle Part Ailleurs. Avec un line-up jeune et tourné vers le néo-métal (Jackson Bandeira à la guitare, Marcelo D. Rapp à la basse et Roy "Rata" Mayorga à la batterie), Max Cavalera accouche d’un premier album éponyme, enregistré sous la houlette de Ross Robinson. Soulfly emprunte le côté tribal cher à "Roots", en y ajoutant un côté plus rentre-dedans et une pincée de hardcore.

Le succès est immédiatement au rendez-vous, mais déjà, les problèmes de line-up commencent. Le premier guitariste s’en va, vite remplacé par l’ex-guitariste de Machine Head, Logan Madder. Ce dernier ne restera que 6 mois, et se fera remercier, au profit de l’ex-Snot, ]. En juillet 1999, c’est Roy Mayorga qui quitte la tribu Soulfly, pour être remplacé par Joe Nunez.

"Primitive" voit le jour à la fin 2000, et va encore plus loin dans le nombre d’invités. Tom Araya (Slayer), Chino Moreno (Deftones), Grady Avenell, Corey Taylor (SlipKnoT) font de cet album primitif un melting pot musical, à la manière des productions hip hop. Dès la fin de la tournée, en juillet 2001, le dernier batteur en date quitte Soulfly, pour des raisons financières (il n’était payé qu’en tournée). La tribu a décidément des problèmes de stabilité, et on peut craindre pour son avenir à ce moment précis…

Roy Maryorga, parti un temps faire mumuse chez Medication, rejoint finalement ses anciens camarades pour enregistrer "III", et réintègre peu après le groupe en tant que membre à plein temps. Ce troisième album, produit par Max Cavalera himself, marque un retour au son des débuts de Soulfly, mais bien que très efficace, on sent que la formation tourne en rond, et que les compositions manquent cruellement d’originalité. Les thèmes abordés sont sempiternellement les mêmes (la mort de Dana par exemple), et certains morceaux se ressemblent comme deux gouttes d’eau ("Downstroy" et "Eye For An Eye""). Le groupe, largement mis en avant par le label Roadrunner, entame néanmoins en juin 2002 une tournée qui s’avère être un véritable succès. Après un an de promotion, le groupe rentre enfin à Phoenix, pour commencer à composer un quatrième album, qui incorporera selon les dires de Max, de nombreuses percussions provenant d’Afrique du Nord...

Mais tous ces plans sont interrompus par un véritable coup de tonnerre en septembre 2003 : après que Gloria Cavalera ait voulu virer Marcelo D. Rapp du groupe, Roy "Rata" Mayorga et Mikey Doling ont soutenu leur collègue en quittant le groupe (pour former Abloom). Maxou réagit vite, en embauchant immédiatement des pointures telles que Marc Rizzo (ex-Ill Niño), Bobby Burns (ex-Primer 55) et Joe Nunez (ex-Soulfly…) pour donner quelques concerts fin septembre. Il se justifie de la manière suivante : "Je n'ai jamais voulu que Soulfly devienne un groupe comme Metallica, avec les quatre mêmes musiciens. Le line-up de Soulfly a changé sur chaque album et il est probable que ça continue ainsi. Pour arriver à ce que je voulais, il fallait que je reprenne tout au début, que je trouve des gens dignes d'intérêt, avec qui je n'avais jamais joué pour créer ceci".

"Prophecy", le quatrième album enregistré dans la foulée au studio Salt mine de Phoenix, sort fin mars 2004. Dave Ellefson, le bassiste mythique de Megadeth, y fait une apparition très remarquée, de même qu’Asha Rabouin (déjà présente sur "Primitive" et "III") et le groupe hongrois Eyesburn. Ce disque marque un véritable aux sources pour Max, avec plusieurs titres possédant la hargne de "Chaos A.D.". Mais surtout, Soulfly semble prendre une nouvelle envergure, en se détachant de la scène métal traditionnelle : le flamenco, le reggae, le dub mais aussi le R’n’B ont tout autant leur place sur ce disque que le tribe métal d’antan. La musique expérimentale et les vibrations world sont ainsi plus présents que jamais dans la musique de Soulfly. "Quand tu arrives au morceau "I Believe", l'album prend un aspect différent. C'est un morceau très spirituel, tout en étant un des plus heavy. Il parle de ma foi ainsi que de celle des fans. C'est un morceau ouvert que je voulais écrire depuis longtemps, avec une partie parlée au milieu. C'est ma propre confession, l'affirmation de ma foi en Dieu, ma croyance…".

Max Cavalera est donc une sorte d’OVNI dans le petit monde du métal : n’hésitant pas à se débarrasser de son personnel au moindre problème, il évolue à un rythme effréné, enchaînant les albums et les tournées sans faiblir. Adepte des expérimentations, Max continue à se frayer son petit chemin sur la scène métal de plus en plus formatée. Je serais vous, je ne me ferais pas prier pour voir ce que ça donne en live, lors de la tournée française de juin 2004…