Бразильский вокалист и гитарист Макс Кавалера основал Soulfly после своего ухода из группы Sepultura в 1996 году.
1996—1997 годы были чрезвычайно трудными для Макса. Он оставил группу Sepultura, одним из основателей которой он являлся, в знак протеста на увольнение его жены, а также менеджера группы, Глории Кавалеры, остальными участниками команды. К тому же он тяжело переживал трагическую гибель своего приемного сына и одного из лучших друзей — Даны Уэллса (англ. Dana Wells). В 1997 году Макс занялся созданием нового музыкального проекта, который позже получил название Soulfly. Первый состав группы включал, кроме него, нью-йоркского барабанщика Роя Майоргу (англ. Roy Mayorga), гитариста Джексона Бандейру (англ. Jackson Bandeira) и басиста и бывшего дорожного техника Sepultura Селло Диаса. На веб-сайте группы Макс Кавалера сказал, что основал группу «с идеей комбинировать звуки и различные религии».
Первым выступлением ещё никак не названного коллектива стал концерт в Финиксе, штат Аризона, посвященный памяти Даны Уэллса, приемного сына Макса, погибшего в августе 1996 года. Концерт состоялся ровно через год после гибели, 16 августа, и назывался Soulfly Show.
1 октября 1997 года в калифорнийской студии Indigo Ranch началась работа над материалом для первого альбома. Процесс проходил под руководством продюсера Росса Робинсона. Помимо основного состава Soulfly, в записи альбома приняли участие многие друзья Макса: Дино Касарес , Бёртон Белл , Кристиан Уолберс (Fear Factory), Фред Дёрст и DJ Lethal (Limp Bizkit), Чино Морено (Deftones), Бенджи Веббе (Dub War, Skindred), Эрик Бобо (Cypress Hill) и другие. Приглашать музыкантов из других групп на запись альбома стало потом для Soulfly традицией.
31 числа того же месяца музыканты вышли из студии уже с готовыми для сведения треками. После чего Макс отправился в Нью-Йорк, где за обработку материала взялся Энди Уоллес. Таким образом, в январе 1998 года пластинка была готова к тиражированию, упаковке и развозке по магазинам. Оставалось лишь дать название группе. В итоге Макс посредством французского телеканала Canal + обнародовал название своей команды, «Soulfly». Произошло это сразу после выступления Макса с группой Deftones в 1997 году, вместе с музыкантами которой он записал песню «Head Up», вошедшую в альбом Deftones «Around The Fur» и посвященную памяти погибшего Даны.
Альбом вышел в свет 21 апреля 1998 года на Roadrunner Records и достиг 79 позиции в чарте Billboard 200. После записи альбома Джексон Бандейра вернулся в Бразилию (помимо Soulfly он играл в группе Nacao Zumbi), а его место занял Логан Майдер (англ. Logan Mader) из Machine Head. В том же году Soulfly отыграли на фестивале Ozzfest на главной сцене вместе с группами Ozzy Osbourne, Megadeth, Tool, Limp Bizkit, Sevendust и Coal Chamber. После окончания турне Логан Майдер был заменен на Мики Долинга (англ. Mikey Doling), гитариста группы Snot.
После майских концертов в 1999 году в Санкт-Петербурге и Москве, Макс Кавалера вместе с женой Глорией и детьми отправился в Сибирь, в город Омск к сестре своей матери.
Второй альбом группы, «Primitive», c самым большим влияниям нью-метала появился в 2000 году, он оказался самым успешным альбомом группы и достиг 32 номера в Billboard в [США] и 11 места в чартах Англии. Во время записи Джои Нуньез (англ. Joe Nunez), барабанщик из Чикаго, заменил Роя Майорга на ударных. Как и предыдущий альбом, «Primitive» помогали записывать гости из различных групп — Кори Тейлор (Slipknot, Stone Sour), Шон Леннон, Чино Морено (Deftones), Том Арайя (Slayer), Грейд Ивнейл (Will Haven) и другие музыканты. Продюсировал альбом Тоби Райт. В разработке арт-дизайна альбома принял участие Невилл Гаррик, долгое время работавший с Бобом Марли.
Третий альбом Макс Кавалера продюсировал сам, он вышел 25 июня 2002 года и достиг 46 позиции в чарте Billboard 200. При записи пластинки не обошлось без изменений в составе группы, Рой Майорга вернулся на ударные. Также в записи участвовали Кристиан Мачадо (Christian Machado) из Ill Niño, Денни Марианино (Danny Marianino) из North Side Kings, Уилли Армет (Wiley Arnett) и Грег Холл (Greg Hall) из Sacred Reich, и племянник Макса Ричи Кавалера (Richie Cavalera).Альбому было дано странное название 3.
Тур в поддержку альбома продолжался больше года, группа объехала Северную Америку и Европу, играя на одной сцене с In Flames, Slayer и Will Haven. В сентябре 2003 года, после окончания тура, Долинг, Диас и Майорга покинули Soulfly, оставив Кавалеру единственным её участником.
В октябре 2003 Кавалера собрал новый состав Soulfly. Джои Нуньез вернулся на ударные, новым гитаристом стал Марк Риззо, бывший участник Ill Nino. В записи участвовало одновременно два басиста — Дэвид Эллефсон, экс участник Megadeth, и Бобби Бёрнс из Primer 55. Таким образом Макс попытался совместить старую и новую школы метала на альбоме.
Часть альбома была записана в Сербии, с местными музыкантами из Eyesburn (трек «Moses»). Денни Марианино и Аша Рабуин (Asha Rabouin) также участвовали в записи, как приглашенные вокалисты. Продюсировал альбом сам Кавалера.
Prophecy был издан 30 марта 2004 года и в апреле того же года достиг 82 позиции в чарте Billboard 200 и вершины топ 50 Австралийских чартов. Очередной мировой концертный тур проходил при участии групп Black Sabbath, Ill Nino и Morbid Angel.
В феврале 2005 года, Soulfly издали свой первый DVD, названный The Song Remains Insane. Это был биографический взгляд на группу, который содержал концертные выступления коллектива по всему миру, интервью и все видеоклипы группы на то время. В августе 2005 года Roadrunner Records переиздали первый одноименный альбом группы в честь празднования 25-летия лейбла.
В декабре 2004 года началась запись пятого альбома Soulfly — Dark Ages. Тогда же произошли трагические события с близкими Кавалеры: 8 декабря во время концерта в Коламбусе, штат Огайо, был застрелен близкий друг Макса, гитарист группы Pantera Даррел Эббот (Darrell «Dimebag» Abbott). 10 декабря скончался 8-месячный внук Макса и Глории Мозес. В процессе записи Dark Ages Кавалера посетил Сербию, Турцию, Россию, Францию и США, где записывал различные треки вместе с местными музыкантами. Основной состав Soulfly периода Dark Ages: Кавалера, Риззо, Нуньез, Бернс. Также участвовали Дэвид Эллефсон, вокалист группы Eyesburn Койот (Coyote), Билли Милано (Stormtroopers Of Death), Павел «Паштет» Филиппенко (FAQ), Ричи Кавалера (Incite). 4 октября 2005 года состоялся релиз альбома. Многие критики назвали Dark Ages возвращением Макса Кавалеры к thrash metal корням ранних дней Sepultura. Последовавший концертный тур прошел при поддержке таких групп, как Deftones, Korn, Throwdown, Skindred. Soulfly посетили Северную и Южную Америку, Европу, Россию и Австралию.
17 августа 2006 года Soulfly отыграли на 10th Annual D-Low Memorial show. Впервые со времен ухода Макса из Sepultura, на одной сцене с ним выступил его брат — Игорь Кавалера. Братья исполнили один из главных хитов Sepultura — «Roots Bloody Roots», а также «Attitude».
После окончания концертов в поддержку Dark Ages, члены группы сосредоточились на сторонних проектах. Кавалера, вместе с Мэтом Таком (Matt Tuck), вокалистом Bullet For My Valentine, участвовал в записи сингла группы Apocalyptica «Repressed», в январе 2007 года посетил Россию, где отметился на альбоме московской группы FAQ, отыграл в Сербии совместно с System Of A Down. Марк Риззо со своим проектом в стиле фламенко-метал (flamenco-meets-shred metal) путешествовал по Северной Америке. Бобби Бернс приобрел студию в Орландо и также работал над сольными проектами (Love Said No, King Street).
29 июля 2008 вышел шестой альбом Soulfly, который был назван Conquer.
6 ноября 2009 года SOULFLY вошли в студию Edge Of The Earth в Голливуде, штат Калифорния, чтобы приступить к записи седьмого альбома, который получил название Omen. Альбом вышел 25 мая 2010 года на Roadrunner records. На альбоме присутствуют два гостевых вокалиста. В песне «Rise of the Fallen» участвует Грег Пусиато — вокалист The Dillinger Escape Plan, а в песне «Lethal Injection» партии вокала исполнил Томми Виктор из Prong. Группа записывалась с продюсером Логаном Мейдером (также известен по работам с Cavalera Conspiracy, Gojira, Devildriver). Для специальной версии альбома было записано несколько бонусных песен. Soulfly перезаписали песню Sepultura «Refuse/Resist» совместно с Зайоном Кавалерой, также был записан кавер на песню группы Excel «Your Life, My Life».
В июле 2010 из группы ушёл басист Бобби Бёрнс. На его место пришёл Джонни Чоу известный по работе с Cavalera Conspiracy и Fireball Ministry. Во второй половине 2010 года Soulfly отправляются в турне по Европе и Северной Америке.
Летом 2011 года к группе присоединяется в качестве постоянного участника бывший басист Static-X Тони Кампос. Он заменяет на этом посту Джонни Чоу. В августе 2011 года в группу приходит Дэвид Кинкейд из Borknagar, который заменяет Джо Нуньеза.
13 марта 2012 вышел 8 студийный альбом Soulfly, названный Enslaved.
В октябре 2012 года стало известно, что Дэвид Кинкейд уходит из группы после завершения турне. Во время североамериканского турне в начале 2013 года на ударных будет играть сын Макса Зайон Кавалера (Zyon Cavalera).
В мае 2013 года группа объявила о переходе на лейбл Nuclear Blast, на котором группа и планирует записать свой девятый альбом.
Альбом под названием "Savages" вышел в начале октября 2013 года на Nuclear Blast Entertainment. CD продюсирует Терри Дэйт (Terry Date), который известен по работе с Pantera, Deftones, Soundgarden и многими другими. Барабаны на новом альбоме записал сын Макса Кавалеры - Зайон, который присоединился к группе в качестве гастрольного музыканта во время североамериканского турне.
Весной 2014 года Soulfly, совместно с Korn, представили российской публике свой новый альбом. В рамках тура музыканты выступили в Санкт-Петербурге, Москве, Минске, Красноярске, Новосибирске, Екатеринбурге, Уфе, Нижнем Новгороде, Воронеже, Ростове-на-Дону и Краснодаре.
Archangel — десятый студийный альбом грув-метал/трэш-метал-группы Soulfly, выпущенный 14 августа 2015 года на лейбле Nuclear Blast Entertainment. Это последний альбом в составе группы для Тони Кампоса, ушедшего в Fear Factory. Альбом дебютировал на 130 в чарте Billboard 200.
