La prima testimonianza della cattedrale dedicata a san Clemente papa risale alla fine del V secolo. Si tratta di una lettera, datata all'anno 496, di papa Gelasio al vescovo Bonifacio in cui ordina la riconsegna di un servo che si era rifugiato nella cattedrale al padrone, il nobile Pietro, dopo che egli avesse giurato che non lo avrebbe punito. La basilica fu trasformata in età cristiana e intitolata a Clemente I, pontefice dall’anno 91 al 101.
Dichiarata basilica il 2 marzo 1804 da Pio VII, si presume innalzata in età paleocristiana, verso il 327, ai tempi di papa Silvestro, sulle rovine di una basilica romana o del tempio di Marte citato da Svetonio (presenza avvalorata da una favissa, rinvenuta nel 1925 durante i lavori per la costruzione del portico) contenente ex voto fittili. Alcune basi di colonne sono visibili sotto il pavimento della chiesa.
Nel XIII secolo subì una profonda ristrutturazione: furono aggiunte l’abside poligonale esterna e la cappella sotterranea nella quale sono conservate le reliquie dei santi Eleuterio e Ponziano.
Gli stipiti della porta d’accesso laterale, formati da due lesene di marmo bianco decorati da bassorilievi raffiguranti arredi liturgici (messale, croce, brocca per lavabo, aspersorio) alternati con teste di Serafini e coronati da rosette (stemma de cardinal vescovo Riario) scolpiti nel 1512 da Trojano da Palestrina.
Sotto l’abside è la cripta, dove nel 1250 (durante il pontificato di Alessandro IV), furono traslate le reliquie dei santi Eleuterio vescovo e Ponziano papa dal monastero di Tivera, distrutto un secolo prima dai Normanni. Nonostante numerosi restauri conserva colonne con basi, fusti e capitelli di varie epoche e stili raccolti nel territorio, la mensa dell'altare con piastrini del quinto secolo.
Poche le tracce di raffigurazioni tra cui, nella parete a destra dell’ingresso, il trasporto dei corpi dei santi Eleuterio e Ponziano del 21 maggio 1254 alla presenza dei consoli, del vescovo, del capitolo della cattedrale e del podestà (raffigurato con la verga in mano).
I grandi pilastri furono innalzati nel 1595 per rinforzare le volte con la costruzione dei due altari maggiori [nella chiesa vi erano 20 altari!] e nel 1679 della grandiosa tribuna marmorea con il tempietto superiore.
L'altare è a due mense, quella anteriore formata da una lastra di porfido di riutilizzo ornata agli spigoli da pilastrini frammentari con motivi a treccia viminea e a maglie circolari annodate, tipici dell'VIII e IX secolo provenienti da un altro manufatto del secolo XIII.
Il pavimento è formato da frammenti marmorei e resti dell'antico pavimento della chiesa, quadri di laterizio e cocciopisto.