Cádiz, det grekiska Gadeira (τὰ Γάδειρα), feniciernas Gadir ( גדר"fästning"), grundlades omkring 1100 f.Kr. av fenicierna som använde den vid sin handel med stadsstaten Tartessos. Enligt en grekisk legend grundades staden av Herkules efter hans tionde storverk. Under forntiden fanns ett tempel till den feniciske guden Melqart i Cádiz.

Sedan hamnade Cádiz under Kartago och var Hannibals militärbas när han besegrade södra Iberiska halvön. Därefter erövrades staden av Scipio Africanus, som kallade staden Gades, för Roms räkning (206 f.Kr.). Rom använde staden som marinbas. Under kejsar Augustus tid fanns fler än 500 equites i Cádiz; fler fanns bara i Rom och Padua. Det blev huvudstad i den romerska provinsen Augusta Urbs Julia Gaditana.

Vid romerska rikets fall bemäktigade sig visigoterna staden, varefter de antika byggnaderna förstördes, och det finns därför få fornlämningar av betydelse. Från dem erövrades staden 711 av morerna; 1262 blev spanjorerna herrar över densamma under Alfons X av Kastilien. Staden upplevde en renässans sedan Christopher Columbus avreste därifrån till Amerika på sin andra och fjärde resa. Därefter blev det ett centrum för den spanska handelsflottan. 1587 belägrades staden i tre dygn av engelsmannen Francis Drake. Staden intogs därefter ett flertal gånger av England, innan slaget vid Cádiz 1707 då de slutligen besegrades. Under alla dessa anfall skövlades staden.

 Försvar av Cádiz mot engelsmännen, av den spanske konstnären Francisco de Zurbarán, 1634 (Pradomuseet, Madrid).

Under 1700-talet överfördes den spanska handeln från Sevilla till Cádiz, vilket innebar guldår för staden. Under den epoken blev det en av landets största kosmopoler, med betydande invandring från bland annat Irland. Större delen av stadens historiska bebyggelse kommer från denna era. Guldåren tog slut med att Lord Nelson för England återigen anföll mot slutet av århundradet. Staden var en av de få som lyckades behålla sin frihet när Napoleon I stred om det europeiska herraväldet.

Cádiz Cortes (parlament) blev under början av 1800-talet centret för den liberala oppositionen mot Joseph Napoleon Bonaparte och 1812 antogs den spanska konstitutionen där. Detta ledde så småningom till att Ferdinand VII av Spanien fängslades där, vilket blev upptakten till slaget vid Trocadero (1823). 1868 var Cádiz utgångspunkten för den revolution som störtade Isabella II av Spanien. Efter införandet av federativ republik (1873) blev de socialistiska intransigenterna herrar över staden, vilken dock samma år befriades av regeringstrupperna.

Det romersk-katolska stiftet Cadiz y Ceuta tillhör ärkestiftet Sevilla, och grundades 1263 efter Reconquista. Stiftets mest kända person i historien är sannolikt Juan de Torquemada.