A brazil Sepultura 1996. őszén bekövetkezett kettészakadását követően a már hosszabb ideje az arizoniai Phoenix-ben élő, Max Cavalera énekes/gitáros új bandát toborzott, melynek a Soulfly nevet adta.

Marcelo Dias basszer, Lucio Bandeira gitáros, valamint Roy Mayorga (ex-Thorn) dobos formálta társulat ’98 tavaszán rukkolt elõ bemutatkozó albumával. A Ross Robinson hangmérnök keze nyomát viselő, törzsi groove-okra épített, extrém Metal korongon számos közreműködő bukkant fel, mint Chino Moreno (Deftones), Fred Durst (Limp Bizkit), vgay a brazil Crossover legenda, a Ratos De Porao tagjai.

A csapat hamarjában hosszú turné-körútra indult, miközben Lucio gitáros helyére, előbb a Machine Head frissen menesztett bárdistája, Logan Mader, majd a kaliforniai Snot volt gitárosa, Mike Doling került. A koncersorozat végén Roy Mayorga dobos is kiszállt, kinek utódja Joe Nunez, a chicagói Fleshold egykori ütőse lett.

2000. őszén „Primitive” címmel készült el a második Soulfly lemez, amely ismét tucatnyi jónevű zenészkolléga – Tom Araya (Slayer), Corey Taylor (Slipknot), Grady Avenell (Will Haven) és még sokan mások – vendégszereplésével látott napvilágot. Rövid kitérőt követően Roy Mayorga végül visszatért, így Max és kísérete háborítatlanul folytathatta útját, majd 2002-ben került a boltokba, a szimplán „3” címmel ellátott vadiúj lemez.

2004. elején látott napvilágot a legfrissebb Soulfly sorlemez, amely a „Prophecy” címet viseli és Marc Rizzo gitáros, Bobby Burns bőgős, illetve Joe Nunez dobos szereplésével készült. Vendégként ezúttal Dave Ellefson, a Megadeth egykori basszusgitárosa bukkant fel.

2005. év elején egy DVD-t dobtak piacra, „Songs Remains Insane” címmel, mindeközben már elkezdtek új albumuk anyagán dolgozni, ami október első napjaiban „Dark Ages” címmel került a lemezboltok polcaira. Az új Soulfly albumot sokan a zenekar egyik legkiforrottabb és legütősebb anyagának tartanak. A két Cavalera testvér közel 10 év után elásta a csatabárdot,amit legelőször a X.D-Low Memorial Fest-en lehetet tapasztalni.

Mivel Cavalera-ék előadtak két Sepultura klasszikust (Roots Bloody Roots,Attitued). Ezután megalapították Cavalera Conspiracy-t amivel egy kis turnét is lecsaptak. Sokan féltek mi lesz a Soulfly-al,de megnyugtatásukra,hogy a banda nem áll le bele kezdtek az új album munkálataiba. Az új album Conquer címen jelent meg 2008-ban amit Maxx egyiptomi utazása ihletett. Ami a Dark Ages-nél is súlyosabbra sikeredett.