Le groupe groove/thrash metal Soulfly a été créé par Max Cavalera (chanteur, guitariste, compositeur) en 1996 lorsqu'il a quitté Sepultura. Il était co-fondateur de ce groupe qui a laissé une trace très visible dans le monde de la musique metal. Pour ce qui est de Soulfly, Cavalera a décidé de réunir un alignement composé de Roy "Rata" Mayorga (ex-Thorn) à la batterie, Jackson Bandeira (ex-Chico Science) comme second guitariste et Marcello D. Rapp à la basse. Rapp avait déjà été avec Sepultura pour aider sur la route.

Le premier opus était éponyme et il a été mis en vente lors de l'été 1998. L'album présente les musiciens invités Mario C., Burton C. Bell, Dino Cazares et Christian Olde Wolbers de Fear Factory, Fred Durst et DJ Lethal de Limp Bizkit, Chino Moreno de Deftones, Benji Webbe anciennement de Dub War et maintenant Skindred, Eric Bobo de Cypress Hill et Jorge DuPeixe et Gilmar Bola Oito de Chico Science. L'album a été enregistré à l’Indigo Ranch Studios à Malibu, Californie, et produit par Ross Robinson. Pendant cette période, Calavera a participé à de nombreux événements, et il a même été invité sur "Around the Fur" de Deftones.

Le second album de Soulfly porte le nom de "Primitive" et il a vu le jour à l'automne 2000. Le disque a reçu des critiques divisées de la part du public. Plusieurs musiciens étaient invités et la touche plutôt nu metal dans les paroles n'avait pas fait le bonheur des amateurs. Par contre, c'est le disque qui a obtenu le plus grand succès dans les palmarès avec une 32e position du top 200 Billboard et une 11e position dans les palmarès indépendants américains. Joe Nunez remplace Roy Mayorga à la batterie pour cette offrande. Les invités sur l'album sont le chanteur Corey Taylor de Slipknot, Sean Lennon, Chino Moreno de Deftones, Tom Araya de Slayer, Grady Avenell anciennement de Will Haven, Cutthroat Logic, et Asha Rabouin et il a été produit par Toby Wright. La pochette a été réalisée par le même artiste de Bob Marley, soit Neville Garrick. Pour en faire la promotion, il a fait plusieurs tournées mondiales avec Pantera, Morbid Angel et le Ozzfest.

À la fin 2001, Joe Nunez quitte pour joindre Stripping the Pistol. Roy Mayorga quitte son groupe Medication pour rejoindre Cavalera, Doling, et Dias pour l'enregistrement du nouvel album. Cavalera s'est occupé de la production de l'album "III". Christian Machado de Ill Niño, Danny Marianino de North Side Kings, le guitariste Wiley Arnett et le batteur Greg Hall de Sacred Reich, Ritchie Cavalera ont tous collaboré sur l'album III. L'album s'est hissé en 46e position sur le Billboard 200 de la même année.

Après la sortie de "III" le 25 juin 2002, Soulfly a fait une tournée en Europe et en Amérique du Nord avec des groupes tels que Slayer, In Flames, God Forbid, et Will Haven. En septembre 2003, après la tournée mondiale pour "III", Mikey Doling, Marcello Dias, et Roy Mayorga ont quitté le groupe, donc Cavalera est demeuré le seul membre pendant près de trois semaines.

En octobre 2003, Cavalera recrute de nouveaux membres pour l'enregistrement de l'album "Prophecy". Joe Nunez était de retour derrière la batterie, Marc Rizzo (ex: Ill Niño) à la guitare et Bobby Burns (ex: Primer 55) à la basse. David Ellefson, anciennement de Megadeth, a collaboré pour plusieurs pièces à la basse sur l'album. Soulfly est revenu en 2004 avec la sortie de "Prophecy". En février 2005, Soulfly distribue son premier DVD nommé "The Song Remains Insane". Il y a du matériel live d'un peu partout autour du globe, des entrevues et les vidéoclips de la formation. En août 2005, Roadrunner Records remet en vente le premier album dans le cadre de son 25e anniversaire.

En octobre 2005, le cinquième album, "Dark Ages", est mis en vente. L'alignement continuait de changer et les membres sont devenus, en plus de Cavalera, Bobby Burns (basse), Marc Rizzo (ex-Ill Niño)(guitare), et Joel Nunez (batterie). D'ailleurs, Nunez a joué sur l'album "Primitive". En 2007, Cavalera débute un nouveau projet avec son frère Igor, également l'ancien batteur de Sepultura, nommé Cavalera Conspiracy. En 2008, ce projet distribue l'album "Inflikted" sur Roadrunner Records.

Cependant, Soufly revient à la charge avec son sixième album, "Conquer", en juillet 2008 sur Roadrunner Records.