Po odejściu Lamouniera, obowiązki wokalisty przejął Max Cavalera, piszący teksty piosenek od początku istnienia zespołu. Skład uzupełnił gitarzysta prowadzący Jairo T, który swoimi umiejętnościami przyczynił się do dalszego rozwoju grupy.
thumb|Pierwotny perkusista Igor Cavalera W 1985 zespół podpisał kontrakt z wytwórnią Cogumelo Records, która wydała ich pierwszą EP-kę zatytułowaną Bestial Devastation (utwory nagrano w sierpniu 1985 studio JG w Belo Horizonte). Tenże materiał został pierwotnie wydany 1 grudnia 1985 na albumie łączonym (split) wraz z płytą Século XX grupy Overdose. Okładkę tego albumu stworzył znajomy członków zespołu, który opracował też pierwsze logo Sepultury. W tym czasie członkowie formacji przyjęli pseudonimy, które ostatecznie nie przyjęły się na dłużej (Max – Possessed, Igor – Skullcrusher, Jairo – Tormentor, Paulo – Destructor). Na EP-ce zespół prezentował ciężkie, prymitywne death metalowe brzmienie, inspirowane dokonaniami grup Slayer, Sodom, Kreator, Hellhammer. Materiał znamionował także black metalowe wpływy. Po wydaniu EP-ki Sepultura zagrała kilka koncertów w Brazylii (średnio co kilka tygodni, a nawet tylko jeden miesięcznie), m.in. w Recife, a także u boku Overdose. Ich występy zyskały pozytywne przyjęcie nie tylko z uwagi na nazwę, ale także muzykę.