Linn asutati Tüürose foiniiklaste kolooniana ja selle algne nimi oli Gadir. Klassikalise traditsiooni kohaselt loetakse linna asutamisaastaks 1104 eKr ehk 80 aastat pärast Trooja sõja lõppu.[1]

Kreeklased teadsid linna Gadeira (kreeka τὰ Γάδειρα) nime all. Vanakreeka mütoloogias loodi linn Heraklese poolt tema kümnenda vägitöö käigus, kus Herakles röövis Geryoni veisekarja. Geryon elas maailma lääneserval Erytheia saarel, mis oli üks kolmest saarest (Erytheia, Antipolis ja Kotinoussa), mis moodustasid arhipelaagi kohas, kus asub tänapäeva Cádiz.

Aasta 500 eKr paiku langes linn Kartaago kontrolli alla. Cádizist sai Hannibali tugipunkt[2] Lõuna-Ibeeria vallutuseks.

Teises Puunia sõjas Rooma ja Kartaago vahel vallutasid roomlased Scipio Africanuse juhtimisel Cádizi aastal 206 eKr. Rooma perioodil kandis linn nime Gades. Linn koges jõukuse märgatavat kasvu, sinna ehitati akvedukt, amfiteater, templeid jm. Lühikesel ajavahemikul oli see Rooma impeeriumi suuruselt teise elanikearvuga linn; seal resideeris viissada Rooma ülemklasside liiget (ladina eques romanus), mis jäi alla vaid Rooma linnale ja Padovale. [3]

Rooma impeeriumi lagunedes oli linn vaheldumisi vandaalide, bütsantslaste ja läänegootide valduses. Aastal 552 vallutasid bütsantslased Ibeeria poolsaare lõunapoolse osa, mille sisse jäi ka Сádiz, ja hoidsid seda enda käes kuni aastani 620, mil ala läks tagasi läänegootide kätte.

711. aastal algas mauride sissetung Ibeeria poolsaarele ning sama aasta 19. juulil toimus Guadelete lahing mauride ja läänegootide vahel, pärast mida jäi linn mauride valdusse kuni aastani 1262. Mauride ülemvõimu all, vahemikus 711–1262, kandis linn nime Qādis (araabia قادس). Siit lähtub ka linna tänapäevane hispaaniakeelne nimi Cádiz. Mauride perioodil jätkus linna allakäik. Lõhuti seal olnud Heraklese kuju, mis oli linna püstitatud rooma ajal. Mauride perioodist pole tänapäeva Cádizis eriti midagi säilinud.

Aastal 844 möödusid Cádizist taani viikingid oma rüüsteretkel, mis lõppes Sevillas.[4]

Aastal 1262 võeti Cádiz kristlaste poolt rekonkista käigus tagasi, kui Kastiilia kuningas Alfonso X selle vallutas.

Suurel maadeavastuse perioodil seilas Christoph Kolumbus siit oma teisele ja neljandale Ameerika-retkele. Linn oli alguspunktiks paljudele avastusretkedele, koloniaalajastul asusid siit Ameerika poole teele konkistadoorid. Cádizile kuulus kaubandussuhete monopol Ameerikaga, siin asus Hispaania aaretelaevastiku peakontor. See tegi linnast Hispaania vaenlaste olulise sihtmärgi. 1587. aasta aprillis korraldas linnale röövrünnaku Francis Drake.

Cádiz on koht, kus loodi Hispaania esimene konstitutsioon aastal 1812.[5]