1984 yılında Brezilya’nın Belo Horizonte şehrinde kurulan ve Portekizce’de "mezarlık" anlamına gelen Sepultura vokal ve gitarda Max Cavalera, gitarda Jairo T, bas gitarda Paulo Jnr. ve bateride Igor Cavalera’dan oluşan kadrosuyla 1985’te yine Brezilya’lı bir grup olan Overdose ile “Bestial Davastation” isimli bir albüm yaptı. Fakat önemli bir başarı elde edemedi.

1986 yılında çıkardığı “Morbid Visions” isimli çalışmasıyla hatırı sayılır bir başarı yakaladı ve 1987’de “Schizophrenia” albümünü çıkardı. Bu arada gitara Andreas Kisser geçti ve grup daha sert, süratli ve saldırgan bir çizgiye oturdu.

1989 yılında çıkardıkları “Beneath The Remains” albümü ile ismini tüm dünyaya duyurmayı başardılar ve zirveye doğru tırmanmaya başladı. 1991 yılında “Arise”, 1993’te “Chaos A.D.” ve 1996 yılında çıkardıkları “Roots” ile de çıkışını durmadan sürdürdü. Ancak vokal Max Cavalera 1997’de gruptan ayrıldı.Max Cavalera’nın gruptan ayrılması üzerine yerine Derrick Leon Green geldi ve bugüne kadar Derrick’le devam edilmekte.Bir diğer değişiklik ise Cavalera kardeşlerden 2.sinin yani Igor Cavalera’nın gruptan ayrılmasıdır bu da 12.06.2006 tarinde Avrupa turnesinden önce yaptığı açıklamayla gerçekleşmiştir ve yerine Jean Dolabella getiriliştir.

Slayer ve Venom gibi grupların yoğun etkisiyle yola çıkan Sepultura, giderek kendine özgü bir çizgi yakalamayı başardı ve Death metal, Black metal, Thrash metal ve Speed metal karışımı orijinal bir tarz elde etti. 90 kuşağı grupları arasında en sevilen gruplardan biri oldu.

1999 yılında Against’i, 2001’de Nation’ı ,2003’te Roorback’i ve son olarak da 2006’da Dante XXI albümü piyasaya sürüldü.