Soulfly is led by former Sepultura frontman Max Cavalera, who formed the band after he left the Brazilian group in 1996.

Soulfly incorporates many styles of metal with Brazilian tribal and world music, much like Cavalera's previous band Sepultura.

"In addition to the core band, which at the time consisted of Roy Mayorga on drums and percussion, Cello Dias on bass and Lúcio "Jackson Bandeira" Maia on lead guitar, Soulfly featured Burton C. Bell, Dino Cazares and Christian Olde Wolbers from Fear Factory, Fred Durst and DJ Lethal from Limp Bizkit, Chino Moreno from Deftones, Benji Webbe formerly of Welsh band Dub War and now a member of Skindred, Eric Bobo from Cypress Hill, Jorge do Peixe and Gilmar Bola Oito from Chico Science & Nação Zumbi, and Mario C. The album was recorded at Indigo Ranch Studios in Malibu, California, and was overseen by producer Ross Robinson.

After recording the first album, Jackson Bandeira returned to Brazil with Nação Zumbi and was replaced by Logan Mader of Machine Head for the live tour that followed.

After the world tour in support of Soulfly, Logan Mader was replaced by Mikey Doling who had just been displaced by the breakup of Snot.

The album featured a number of guest appearances as well, including Corey Taylor of Slipknot and Stone Sour, Sean Lennon, Chino Moreno of Deftones, Tom Araya of Slayer, Grady Avenell of Will Haven, Cutthroat Logic, Babatunde and Asha Rabouin and was produced by Toby Wright.

Other musicians performing on 3 included Cristian Machado of Ill Niño, and guitarist Wiley Arnet and drummer Greg Hall of Sacred Reich, and Max's stepson Richie Cavalera.

After the release of 3 on June 25, 2002, Soulfly toured throughout Europe and North America with bands such as Slayer, In Flames, God Forbid, and Will Haven.

On the song "Moses", he worked with Serbian band Eyesburn, which also features reggae influences from one of his heroes, Bob Marley.

Danny Marianino and Asha Rabouin returned as guest vocalists on Prophecy, as well, and Max Cavalera produced the album.

Many critics have described Dark Ages as a return to Cavalera's thrash metal roots of the early Sepultura days; however, the world music influence found on the first four Soulfly albums is still present.

In fact, this time, Cavalera traveled to five different countries — Serbia, Turkey, Russia, France, and the United States — in order to record all the sounds that he desired to have on the new album.

The core band on Dark Ages still consisted of Cavalera, Joe Nunez, Bobby Burns and Marc Rizzo, and on this album, Dave Ellefson came back to lend his talents to a couple of tracks, Eyesburn vocalist Coyote sang on "Innerspirit", Stormtroopers of Death vocalist Billy Milano and Russian singer Paul Fillipenko of FAQ screamed on the hardcore influenced "Molotov", and Max's stepson, Ritchie Cavalera from Phoenix-based band Incite, sang on "Staystrong".

Cavalera guested on the Apocalyptica single "Repressed" with Bullet For My Valentine vocalist Matt Tuck during a visit to Germany, went to Russia in January 2007 to guest on the album Circus Dogs by Russian hardcore band FAQ and played on Saint-Petersbourg with Radiohead album sound producer Nike "Naik" Groshin, played a surprise jam session in Serbia with Dan Lilker of Brutal Truth and S.O.D., and spent time in Arizona writing for future releases.

Burns purchased a studio in Orlando, Florida with his partner Tim Lau, revived his former band Primer 55, and worked on new releases for his Love Said No and King Street projects.

In September 2006, Burns suffered a mild stroke, was forced to sit out of Soulfly's North American tour, and his spot in the band was briefly filled by Dave Ellefson and Danny Lilker.

[10] Soulfly entered the Edge of the Earth Studios in Los Angeles, California, on November 6, 2009, to begin recording their seventh album with Max Cavalera and Logan Mader both producing.

[11] Through a series of streaming web video updates, frontman Max Cavalera revealed on November 13, 2009, that the album would be called Omen[12] and would feature guest appearances by Tommy Victor of Prong and Greg Puciato of The Dillinger Escape Plan.

On July 18, 2010, bassist Bobby Burns posted following message on his Twitter profile: "To all the fans... Soulfly and I have decided to part ways.

On July 1, 2011, Soulfly announced that the group had recruited former Static-X and current Asesino, and then Prong, and Ministry bassist Tony Campos into the band, replacing Bobby Burns.

In September 2011, the band announced they entered the recording studio to make their next album due for an early 2012 release.

[17] In the December 2011 issue of Metal Hammer, Cavalera stated that the main theme of the album would be slavery, with song titles "Slave", "Chains", "Legions" (a song about the Roman Empire), "Gladiator", "Redemption of Man by God" (featuring Dez Fafara), and "Revengeance" (with Max's 3 sons featuring: Zyon on drums, Richie on vocals and Igor writing half the guitar riffs).

In April 2013 Max announced Soulfly's intention to record more material after their tour, with producer Terry Date,[20] and confirmed on May 3 that Zyon would perform drums on the album.

Savages features a number of guest vocalists including Igor Cavalera Jr. of Lody Kong, Jamie Hanks of I Declare War, Neil Fallon of Clutch, and Mitch Harris of Napalm Death.

On May 1, bassist Tony Campos announced via his Facebook page that he was leaving Soulfly to join Fear Factory.

[31] In a June 2020 interview on Kazakhstan's "Armatura" podcast, Cavalera confirmed that he had been "writing some riffs" for the twelfth Soulfly album.

"[32] In a May 2021 interview with Finland's Kaaos TV, Cavalera further reiterated the album's progress and confirmed that it would likely not be released before 2022: "We're just working on it.

[34] In August 2021, it was announced lead guitarist Marc Rizzo had left the band,[35] and that his replacement on the 2021 North American tour would be Dino Cazares of Fear Factory.

[38][39] In a January 2024 interview on the "Nu Pod With Joshua Toomey and Ro Kohli" podcast, Cavalera confirmed that he would be "working on new Soulfly this year, writing and hopefully recording" the band's next album for a 2025 release.