Fu edificata nel X-XI secolo su di una pre-esistente chiesa dedicata a Santa Maria del Parco del VII secolo, consacrata da papa Pasquale II nel 1106.
Dopo il disastroso terremoto del 1231, fu ricostruita in sette navate, per poi esser restaurata in stile neoclassico da Pietro Paolo Ferrara. La facciata neogotica del 1903 si affaccia sull'angusta via del Duomo. Dal pronao, si accede, tramite il portale, alla navata centrale.
Lungo le due navate laterali si aprono quattro cappelle per lato contenti altari barocchi in marmi policromi. In fondo all'abside rettangolare, che è rialzata dal resto della chiesa poiché sotto ad essa vi è la cripta o succorpo, si trova l'altare barocco in marmi policromi, mirabile opera di Dionisio Lazzari, sul quale c'è un crocifisso dipinto ottocentesco.
Dietro la chiesa, dove c'era l'entrata della prima chiesa, si trova il Campanile. Si tratta del vero gioiello della cattedrale risalente al XII secolo che non ha subito modifiche nel corso degli anni a differenza del resto del complesso. È opera di Nicola d'Angelo conosciuto anche come Niccolò d'Angelo (autore dell'altare maggiore della Cattedrale di Sutri e soprattutto, insieme al Vassalletto, del candelabro pasquale della basilica di San Paolo fuori le mura e appartenente alla nota famiglia di marmorari romani, detta anche dei Cosmati).
Accanto al suo nome si scorge l'indicazione "romanus", titolo, di cui si fregiavano coloro che a Roma lavoravano, utilizzato dagli artisti per firmare le loro opere (anche nel ciborio della cattedrale di Ferentino, Drudo da T. si definisce "romanus"). La possente mole del Campanile della Cattedrale di Gaeta è in stile arabo moresco ed è costituita da tre piani con bifore sormontati dal cupolino ottagonale. All'interno della strombatura ci sono dei sarcofagi di epoca romana e due bassorilievi marmorei raffiguranti la storia di Giona e del mostro. Il Campanile di Gaeta, insieme a quello di Amalfi con cui ha notevoli analogie, rappresenta un eccellente esempio di arte medievale dell'Italia centro meridionale.