W kwietniu następnego roku ukazał się debiutancki longplay zespołu, zatytułowany po prostu „Soulfly”. Wśród zaproszonych gości, pojawili się między innymi – Mario C. (znany ze współpracy z Beastie Boys), muzycy Limp Bizkit (Fred Durst i DJ Lethal), Chino Moreno (Deftones), a także prawie cały skład Fear Factory (Burton C. Bell, Dino Cazares i Christian Olde). Niedługo potem doszło do pierwszej zmiany personalnej – odszedł Bandeira, a jego miejsce zajął Logan Mader (Machine Head). W tym ustawieniu zespół ruszył w trasę koncertową, pojawiając się także na słynnym Ozzfeście, obok Ozzy’ego Osbourne’a, Megadeth oraz Toola. Po zakończeniu tournee, Madera zastapiono Mikey’em Dolingiem.
Pod koniec września 2000 roku, do sklepów trafił ich drugi album, „Primitive”, którego brzmienie inspirowane było w dużej mierze nu metalem. Wydawnictwo okazało się największym komercyjnym sukcesem formacji na rynku amerykańskim na przestrzeni ich całej dyskografii. Podczas nagrywania materiału, doszło do kolejnego przetasowania wewnątrz składu – na perkusji, zamiast Mayorgi, pojawił się teraz Joe Nunez. I znów dopisali goście – wśród nazwisk na płycie pojawili się między innymi Corey Taylor (Slipknot), Sean Lennon (syn Johna), wspomniany wyżej Chino Moreno oraz Tom Araya (Slayer). Okładkę zaś projektował znany ze współpracy z Bobem Marley’em – Neville Garrick. Płyta ogrywana była nie tylko podczas standardowej trasy koncertowej (z Panterą i Morbid Angel), lecz także na Ozzfeście.
Pod koniec 2001 roku, z Soulfly postanowił odejść Nunez. Wrócił za to Mayorga i wspólnie z Cavalerą, Dolingiem i Diasem przystąpił do pracy nad trzecim krążkiem formacji, zatytułowanym skromnie „3”. Muzyków wspierali ponadto – Cristian Machado (Ill Niño), gitarzysta Wiley Arnett, perkusista Greg Hall, a także pasierb Maxa – Ritchie. Ostatecznie, album ujrzał światło dzienne w połowie kolejnego roku. Podczas tournee, zespołowi towarzyszyły takie sławy, jak choćby Slayer, czy God Forbid.
Jeśli ktoś myślał, że to już koniec zmian personalnych, to we wrześniu 2003 roku doszło prawie do zawieszenia działalności grupy. W tym czasie bowiem, z formacją pożegnali się aż trzej dotychczasowi członkowie – Mikey Doling, Marcello D. Rapp, Roy Mayorga, zostawiając Cavalerę samego. Miesiąc później, powstał jednak drugi skład – wrócił Nunez, który dzielił perkusję z Markiem Rizzo, na basie zagrał Bobby Burns, a partie gitarowe były autorstwa niejakiego Davida Ellefsona, znanego z Megadeth. Dodatkowo, Cavalera postanowił dać ujście swojej fascynacji muzyką świata. W tym celu, muzyk udał się na Bałkany, do Serbii, by tam nagrać tradycyjne lokalne brzmienia. W efekcie, na kolejnej płycie „Prophecy”, pojawili się na nie tylko Cyganie serbscy, lecz także pasterskie instrumenty dęte pamiętające Średniowiecze. Premiera krążka odbyła się pod koniec marca 2004 roku. A na trasie koncertowej – grali na jednej scenie z Black Sabbath i Morbid Angel.
Koniec roku zastał formację w studiu nagrań. Nie był to jednak dobry moment na sesje, gdyż Cavalera zajęty był sprawami osobistymi – na początku grudnia stracił swojego przyjaciela, zastrzelonego w Ohio, a dwa dni później niespodziewanie zmarł jego ośmiomiesięczny wnuk Moses. Była to tak zwana śmierć łóżeczkowa.
Tymczasem, w lutym następnego roku pojawiło się pierwsze DVD grupy, „The Song Remains Insane”. Równocześnie postępowały, choć wolno, prace w studiu. Do wokalisty dołączyli – Rizzo, Nunez, Burns, Ellefson, niejaki Coyote (Eyesburn), Billy Milano (Stormtroopers Of Death), a także wspomniany wyżej Ritchie Cavalera. W efekcie, kolejna płyta Soulfly, „Dark Ages”, ukazała się na początku października. Była ona efektem podróży frontmana, nie tylko do zaprzyjaźnionej Serbii, lecz także Turcji, Rosji, Francji i za Ocean. Krytycy zwracali uwagę, że nowy materiał przypomina powrót muzyka do korzeni thrashu, a mówiąc dokładniej, wczesnej Sepultury. Promocyjna trasa koncertowa (z Deftones, KoRnem, Throwdown i Skindredem) obejmowała Amerykę Północną i Południową oraz Australię i Europę.
Obok działalności w strukturach zespołu, muzycy intensywnie udzielali się także w innych projektach. Cavalera pojawił się gościnnie na singlu Apocalyptiki „Repressed”, koncertował w Europie, a w Stanach Zjednoczonych pracował nad nowymi utworami do przyszłego albumu. Rizzo występował solo w Ameryce, grając mieszankę metalu i flamenco, pracując wytrwale na miano jednego z najlepszych gitarzystów metalowych świata. Ponadto przygotowywał materiał na swoją drugą solową płytę, „The Ultimate Devotion” (pierwsza, „Colossal Myopia”, ukazała się w 2005 roku). Burns tymczasem, wynajął studio w Orlando, gdzie mógł skupić się na swym nowym zespołe.
W marcu 2007 roku, muzycy Soulfly nagrali cover z repertuaru Marilyn Mansona, „The Beautiful People”. Piosenka ukazała się trzy miesiące później. Tymczasem, na początku czerwca, Max i jego brat Igor (po jedenastu latach przerwy) – znów połączyli siły i weszli do studia, rozpoczynając prace nad projektem nazwanym Cavalera Conspiracy. Miesiąc później, wsparci przez Rizzo i Joego Duplantiera (Gojira), nagrali pierwszy longplay nowego projektu – „Inflikted”. Dodatkowo, wśród gości pojawił się także, znany z Pantery, basista Rex Brown. Premiera krążka odbyła się pod koniec marca 2008 roku, a niedługo potem formacja ruszyła w promocyjne tournee.
Równocześnie z sesjami do „Infikted”, powstawał także materiał na szóstą płytę Soulfly. W pewnym momencie doszło do dwumiesięcznej przerwy w nagraniach, gdyż Cavalera wyjechał do Egiptu, by tam szukać inspiracji, które mógłby wpleść w nagrane już kompozycje. Po powrocie, dodawano potrzebne partie, a także miksowano z już istniejącymi i w ten sposób, na początku 2008 roku można było powoli myśleć o działaniach promocyjnych. Wśród zaproszonych gości, na albumie pojawił się Dave Peters (Throwdown) oraz David Vincent (Morbid Angel). Wydawnictwo, zatytułowane „Conquer”, trafiło do sklepów pod koniec lipca 2008 roku. W ramach promocji – grupa ruszyła na tournee, wpierw po Stanach Zjednoczonych, potem również zahaczyła o Europę.
Ich najnowszy longplay, „Omen”, ukazał się pod koniec maja 2010 roku. Gościnnie pojawili się na nim między innymi Greg Puciato (The Dillinger Escape Plan), a także syn Cavalery, Zyon, grający na perkusji.
Machine Head • Sepultura • Beastie Boys • Limp Bizkit • Fear Factory • Ozzy Osbourne • Megadeth • Tool • Slipknot • John Lennon • Slayer • Bob Marley • Pantera • Morbid Angel • God Forbid • Black Sabbath • KoRn • Apocalyptica • Marilyn Manson • The Dillinger Escape Plan • Corruption • Killjoy • Skunk Anansie