Viszonylag sok idő, majd' egy év telik el addig, amíg elindul az Against turné, és ez újabb bizonytalanságot szül a rajongók között. Eközben a megújult zenekar kaliforniai klubokban melegít (Troops Of Doom néven), hogy aztán elsőként a brazíliai Noise Against Hunger jótékonysági fesztiválon 1999. augusztus 15-én mindenkinek megmutathassák: a Sepultura él. A színpadon egymás után tűntek fel a négyes mellett a Sepultura barátai: Mike Patton, Jason Newsted, Carlinhos Brown, vagy a régi harcostárs Jairo. Még a Xavantes törzs tagjai is eljöttek erdei kunyhóikból Sao Paulo sokkoló betondzsungelébe a koncert kedvéért.

Közel egy éven keresztül zajlott az Against Tour, ahol először léptek fel estéről estére a Slayer vendégeként. A turné végeztével gyakorlatilag rögtön nekiláttak egy új album megírásának. A stúdiómunkálatok 2000 őszén kezdődtek és az album a következő év tavaszán jelent meg. A Nation konceptlemez, mely egy olyan világ/nemzet megteremtéséről vizionál, ahol a korrupció felszámolásával, egymás kölcsönös megbecsülésével jobb életet élhetnének az emberek. Mindezt az eddigi legszélesebb zenei eszköztárral mutatják be.

A lemez befogadása viszont nem könnyű feladat, legalábbis a régi Sepu fanoknak biztosan nem az. Minden korábbinál több a belassult pillanat és Derrick is jóval több tiszta dallamot énekel. A mondanivaló erősítésére a dalok között idézetek hallhatók: Gandhi, Albert Einstein, a 14. Dalai Láma és kalkuttai Teréz Anya filozofikus gondolatai. A feszes riffeléshez szokott hallgató figyelme könnyen elkalandozik. Egybehangzó vélemények szerint a lemez legjobb dala a finn Apocalypticával közösen írt és előadott Valtio, ami tulajdonképpen a lemeznyitó Sepulnation egy átirata.

Még januárban a Nation megjelenése előtt fellépnek a harmadszor megrendezésre kerülő Rock In Rio fesztiválon, majd tavasszal indul a szokásos világkörüli turné. A Nation lemezzel a Sepultura kitöltötte szerződését a Roadrunner-nél. 2002 szeptemberében búcsúzóul a Roadrunner kiadja a klasszikus felállás utolsó koncertjét dupla cédén. Nem sokkal utána pedig a banda addigi három VHS anyaga jön ki a Chaos DVD-n, szintén a nagy időkre emlékezve. Az aktuális felállás válaszul a Revolusongs feldolgozás mini-albummal jelentkezik az év végén, igaz csak Braziliában és Ázsiában kapható az anyag. Közben nekilátnak a következő nagylemez megírásának és felvételeinek is, melyet új kiadó, a német SPV gondoz.