Группа была сформирована в Бело Оризонте, Бразилия, в 1984 году братьями Игорем (р. 24 сентября 1970, Бразилия; ударные) и Максом Кавалера (р. 4 августа 1969, Бразилия; вокал, гитара), совместно с Пауло Джейр (р. 30 апреля 1969, Бразилия; бас) и гитаристом Джаиро Гуэдесом. "Sepultura" – по-португальски значит могила, что как раз подходит к определению относительно характера музыки, которая имеет дело с темами смерти и разрушения, навеянными влиянием групп типа "Slayer" и "Venom". В 1985 "Sepultura" записала альбом совместно с бразильской командой "Overdose" (которую "Сепультура" поддерживала во время их первого гига), но этот дебют, "Bestial Devastation", был невысокого качества и не имел широкого распространения.

С выходом их первого сольного диска "Morbid visions" группа поимела большой успех по всей Бразилии и принялась гастролировать по родной стране. Однако вскоре после этого Гуэдес решил покинуть состав "Сепультуры". Команда принялась искать нового гитариста, и, в конце концов, им стал талантливый музыкант Андреас Киссер. В 1987 году выходит диск "Schizophrenia", включающий в себя такие хитовые вещи, как "Escape to the void" и инструментальную пьесу "Inquisition symphony". "Sepultura" становится известной вне Бразилии. В Европе выходит 30-тысячным тиражом бутлег "Шизофрении".

Получив широкую известность, группа подписала контракт с датским лейблом "Roadrunner". После выхода альбома "Beneath the remains" команда предприняла свой первый международный тур. Они гастролируют по Европе, США и Мексике. Став первой всемирно известной бразильской металлической командой, "Sepultura" выступила в качестве хедлайнеров на втором фестивале "Rock in Rio". После этого группа дает 3 гига перед 40-тысячной аудиторией в Сан-Паулу. Во время одного из этих концертов начались беспорядки, и один человек был убит. После этого случая "сепультуровцы" долгое время не давали представлений в Бразилии. Группа отправилась в зарубежное турне. Ее принимали в Греции, Японии, Австралии, Голландии и Индонезии.

В 1993 году вышел альбом "Chaos A.D.", на котором "Sepultura" использовала новые музыкальные идеи. Клип на песню "Territory" пользовался большим успехом в Израиле. В Бразилии группе была вручена награда от "MTV music video awards" за лучший видеоклип года. "Sepultura" стала первой бразильской металлической командой, давшей концерты в России и первой латиноамериканской группой, участвовавшей в фестивале "Монстры рока" в Донингтоне (Англия).

В 1994 году Макс совместно с Алексом Ньюпортом из "Fudge tunnel" замутил параллельный проект "Nailbomb". Новая команда просуществовала недолго, успев записать пару дисков, в создании которых приняли участие Игорь Кавалера и Андреас Киссер. На следующем альбоме "Сепультуры" "Roots" присутствовали элементы бразильской народной музыки, что и следовало из его названия. Большой популярностью с этого альбома пользовались композиции "Roots bloody roots", "Attitude" и особенно "Ratamahatta", видеоклип на которую получил награду "Лучшее рок-видео" на бразильском MTV. Группа опять колесила по всему миру и участвовала в различных фестивалях.

Со временем в группе начались разногласия между Максом и остальными участниками коллектива, в результате которых Макс покинул состав и основал новый проект "Soulfly". Оставшиеся "сепультуровцы" не стали вешать носы, а втроем стали готовить материал для следующего диска. В роли вокалиста попробовал себя Андреас, но у него это не очень получалось, и группа стала подыскивать себе нового певца. Таким человеком оказался Деррик Грин, хорошо вписавшийся в коллектив. К этому времени почти все инструментальные партии для нового альбома были готовы и оставалось только наложить на них вокал, что и было незамедлительно проделано, в результате чего на свет появился "Against", получившийся очень эмоциональным. Тур в поддержку этого альбома прошел очень успешно. Последний диск "Nation" был встречен поклонниками на ура и сразу же получил "золото". Группа отправляется в турне в поддержку альбома. В октябре 1999 года группа выступает в Сан-Пауло на Via Funchal . На концерте присутствовали 4500 фэнов.