Besides leaving one of the most popular heavy metal bands in the world, which he'd co-founded in the early '80s, he also had to deal with the unsolved murder of Dana Wells, his stepson and best friend. Using music as therapy to overcome his depression, Cavalera put together a band that included Roy "Rata" Mayorga on drums (ex-Thorn) and Jackson Bandeira on second guitar (ex-Chico Science), while former Sepultura roadie Marcello D. Rapp rounded out the quartet on bass. Their self-titled debut album was released in the spring of 1998. Besides fronting Soulfly, Cavalera has branched out into other areas usually not associated with heavy metal musicians. He became a much sought-after speaker at music conventions, as evidenced by his appearances at CMJ's New Music Marathon in New York and Holland's Crossing Border Festival, both in late 1997. He also guested on Deftones' breakthrough album, Around the Fur, and signed on to sing a TV commercial for Sprite in his native land of Brazil.

Soulfly's second album, Primitive, was released in the fall of 2000. The album was met with a split reaction, and Cavalera found himself the object of criticism from factions of his fan base. The heavy amount of guest appearances and his preference toward nu-metal lyrics were the main complaints, but Cavalera maintained pride in his work and kept going, hitting the road and touring behind the album. He handled the production for 2002's III, and Soulfly returned again in 2004 with Prophecy. A year later, Roadrunner reissued their self-titled first album as part of the label's 25th anniversary celebration. Soulfly's fifth album, Dark Ages, appeared in October 2005. Continuing his habit of switching up the lineup, Cavalera was backed this time out by bassist Bobby Burns, guitarist Marc Rizzo (ex-Ill Niño), and drummer Joel Nunez, who had previously played on Primitive.

In 2007 Cavalera began collaborating with brother and former Sepultura drummer Igor on a project called Cavalera Conspiracy. The duo made its live debut that August as the opening act for Soulfly, and went on to release an album, Inflikted, for Roadrunner in 2008. Soulfly's sixth full-length offering, Conquer, arrived in July 2008 and was quickly followed by 2009's Omen. After the release of their seventh album, the band went through a sting of lineup changes. The first came in 2010 when bassist Bobby Burns announced he was leaving the band; he was replaced the following year by former Ministry bassist Tony Campos. Drummer Joe Nunez also left the band, and was replaced by Borknagar's David Kinkade shortly before Soulfly went into the studio with producer Zeuss to begin work on new material that would eventually become their eighth album, Enslaved, which was released in 2012.

Throughout that year the band toured their own "Maximum Cavalera" package tour featuring three bands all fronted by members of the Cavalera family -- Soulfly, Incite, and Lody Kong. Drummer Kinkade left the band in 2012, announcing his retirement from performance. For the next album, the band moved from their longtime home of Roadrunner Records to Nuclear Blast, and Cavalera's youngest son Zyon took over on drums. The effort, entitled Savages, was produced by Terry Date and released in October 2013.

The band began recording a follow-up almost immediately with producer Matt Hyde. The finished product Archangel, was issued in 2015, and entered the low end of the charts. Their shortest record at just over 36 minutes, it was also their last with bassist Tony Campos; he left to join Fear Factory shortly after the album's completion. ~ Greg Prato