Edesmenneet rumpali Vinnie Paul ja kitaristi Dimebag Darrell perustivat Panteran vuonna 1981 kitaristi Terry Glazen kanssa. Pian mukaan liittyivät laulaja Donny Hart ja basisti Tommy D. Bradford. Jo seuraavana vuonna Hart ja Bradford lähtivät kuitenkin omille teilleen, minkä johdosta Glazesta tehtiin laulaja ja Rex Brown liittyi bändiin basistiksi. Tällä kokoonpanolla yhtye julkaisi kolme albumia, Metal Magic (1983), Projects in the Jungle (1984) ja I Am the Night (1985). Tyyliltään hard/glam rockia edustaneet levyt eivät saavuttaneet mainittavaa menestystä ja niinpä myös laulaja Glazen ja muun bändin tiet erkanivat. Muutaman laulajaehdokkaan jälkeen Phil Anselmo liittyi bändiin ja hiljalleen Panteran tyyli alkoi muuttua kohti sitä groove metalia, josta se parhaiten tänä päivänä tunnetaan.
Koska yhtyeen alkuaikojen levyt ovat tyylillisesti täysin eri maailmasta kuin yhtyeen tuotanto vuoden 1990 Cowboys from Hell -albumista eteenpäin, monet pitävät Cowboysia bändin varsinaisena debyyttinä, vaikka se onkin virallisesti yhtyeen viides pitkäsoitto. Näin ajattelee myös yhtyeen basisti Rex Brown, joka puhui aiheesta tuoreessa Gibsonin Metal and Monsters -videosarjan haastattelussa.
”Kun Phil tuli bändiin, koko homma kehittyi aivan uudelle tasolle ja bändistä tuli se Pantera, jona se nyt tunnetaan. Siksi me emme koskaan puhu niistä vanhoista levyistämme”, Brown tuumaa.
”Onhan se kiva joskus muistella menneitä ja näin, mutta ne levyt ovat viimeinen asia, joka minulla on aamuisin herätessäni mielessä. ’Oi, muistatko sen biisin ’Nothin’ On (But the Radio) ja sen laulajan?’ Ei hemmetissä! Vihaan sellaisia biisejä, mutta se oli osa kasvuprosessia. Ja koska ne on kerran julkaistu ja niistä on miljoonia bootlegejä, ihmiset ajattelevat, että se on osa bändin historiaa. Ei se ole. Jos Phil ei laula, se ei ole Panteraa. Näin minä asian näen.”
Samaisessa haastattelussa Brown myös muistelee, miten tutustui Vinnie Pauliin ja Dimebag Darrelliin. Brown sanoo olevansa kiitollinen edesmenneille veljeksille ja soittohomille siitä, että nämä pitivät hänet nuoruusvuosina poissa pahanteosta.
”Tapasin Vinnien niihin aikoihin kun liityin bändiin. Hän soitti jazzbändissä, johon olin myös littynyt. Isäni kuoli kun olin hyvin nuori, joten se oli juttu, joka piti minut pois ongelmista. Suuntasin keskittymiseni siihen”, Brow kertaa.
”Vinniellä oli pikkuveli Darrell, joka oli 15 kun tapasimme. Hän ei ollut vielä edes koskenut kitaraan. Sitten joskus siinä vuoden 1981 nurkilla hän lukittautui huoneeseensa yhdeksi kesäksi ja opetteli kaikki Randy Rhoadsin jutut. Kun hän kesän jälkeen taas ilmestyi huoneestaan, hän soitti tavalla, jollaista en ollut koskaan aiemmin kuullut. Hän oli pieni laiha kaveri, jolla oli iso permis. Se oli täydellinen muodonmuutos.”
