A Downt 1991-ben alapította az akkoriban a Panterában zenélõ énekes/dalszerzõ Phil Anselmo, a Corrosion of Conformityben gitározó Pepper Keenan, a Crowbarban muzsikáló Kirk Windstein (gitár) és Todd Strange (basszusgitár), valamint az Eyehategod dobosa, Jimmy Bower. Mivel régi jó barátok voltak, és az underground zenei életben mindannyian elismertnek számítottak, így amolyan szupergroupnak titulálták õket. A kezdeti idõkben egy háromszámos demót készítettek, amelyet úgy terjesztettek, hogy anélkül adogatták a kazettákat a rajongóknak, hogy elmondták volna, õk csinálták ezt a muzsikát. [1][2] A szalag végül bejárta az egész Egyesült Államok-at, és a csapat adott is egy kis koncertet New Orleans-ban. Az Elektra Records nevû lemezkiadó egyik munkatársa felfigyelt a bulira, és miután megtudta, kik is alkotják a zenekart, leszerzõdtette õket.A Down debütáló lemeze, a NOLA 1995. szeptember 19-én jelent meg, és rögvest az 55. helyen nyitott a Billboard 200 listáján, majd késõbb platinalemez lett belõle. Az album (és az olyan nagyszerû dalok, mint a „Bury Me In Smoke”, a „Lifer”, a „Stone The Crow” vagy az „Eyes Of The South”) szinte azonnal hivatkozási alappá váltak a Black Sabbath-alapú, súlyos, southern-doom-sludge zenék hívei körében, és mind a mai napig ezt tartják a gárda legjobb munkájának.