Jednocześnie muzyk przyjął plemienny charakter całego projektu, bliski jemu od wydania albumu Roots z 1996.
Początkowo, jeszcze nie nazwany projekt, w 1997 był oparty na jammowaniu muzyków. Nazwę swojej nowej grupy Soulfly ujawnił Cavalera spontanicznie w wywiadzie telewizyjnym po występie z Deftones w Paryżu. Do projektu zaprosił muzyków, którymi byli kolejno: basista Marcelo Dias (były specjalista od oświetlenia przy Sepulturze) i perkusista Roy Mayorga (występował poprzednio w Horn i Nausea) i Lucio Maia vel Jackson Bandeira (Nação Zumbi). Razem odbywali próby w Phoenix (w tym mieście mieszkał Cavalera), zaś w nagraniach materiału demo uczestniczyli też dwaj członkowie Nação Zumbi, odpowiedzialni za bębny. Zawierające dwie piosenki demo („Eye for an Eye” i „Primitive”) zostało natychmiast zaakceptowane przez wytwórnie Roadrunner Records. Został podpisany kontrakt i rozpoczęto nagrania w studio Indigo Ranch w kalifornijskim Malibu (tak samo jak Roots). Producentem albumu był Ross Robinson, a miksowaniem zajmował się Andy Wallace (tak samo jak w przypadku Roots). Całe wydawnictwo, nazwane Soulfly i wydane 21 kwietnia 1998, zostało poświęcone pamięci Dany „D-Low” Wellsa. Na albumie pojawiło się wielu gości, m.in. muzycy Fear Factory, Limp Bizkit, Chino Moreno.