Per secoli la Basilica di Santa Pudenziana è stata considerata la più antica chiesa cristiana di Roma. La chiesa sarebbe stata costruita sulla domus del senatore romano Pudente, della quale sono stati rinvenuti i resti sotto la basilica. Il senatore, insieme alle sue due figlie Pudenziana e Prassede, sarebbe stato convertito dall'apostolo Pietro e la sua casa fu presto trasformata in domus ecclesiae, ovvero un edificio destinato ai riti cristiani. Origine e datazione della chiesa, pur antichissima, sono ancora dibattute. Tuttavia, negli atti del sinodo romano del 499 (Sinodo di Papa Gelasio I), la chiesa legata al Titolo di Pudentis (Santa Pudenziana) è menzionata tra le basiliche romane di antica fondazione, confermandone l'importanza e l'antichità già nel V secolo.

Nell'817, Papa Pasquale I trasferì numerosi corpi di santi martiri dalle catacombe romane per renderli più accessibili ai fedeli, collocandoli onorevolmente in varie chiese di Roma. Questa importante opera di traslazione favorì la venerazione pubblica e trasformò il culto dei martiri. Fu così che le reliquie di Santa Pudenziana giunsero nella chiesa di Via Urbana dedicata al padre Pudente.

La struttura attuale della chiesa risale al IV secolo. La ristrutturazione del XVI secolo, opera di Francesco Capriani detto il Volterra, modificò l'interno della basilica creando una navata unica e una cupola a base ellittica sopra l'altare, affrescata dal Pomarancio.

Unica traccia dell'antichissimo passato della basilica è lo straordinario mosaico absidale realizzato tra il 410 e il 417 d.C. durante il pontificato di Papa Innocenzo I. Nonostante il rifacimento della cupola abbia comportato il taglio delle ultime due figure degli apostoli (che sono quindi dieci e non dodici), il mosaico è rimasto intatto nella sua bellezza.

L'iconografia è quella del Cristo Pantocratore, raffigurato maestoso in trono con la mano destra benedicente (tre dita unite per la Trinità) e la mano sinistra che regge il Vangelo, circondato dagli apostoli e da due donne che incoronano Pietro e Paolo, identificabili con le sante Pudenziana e Prassede. Sullo sfondo si intravede il profilo di una città, probabilmente Gerusalemme. Al centro del mosaico si staglia una croce ricoperta di gemme su un monte, forse il Calvario. Accanto alla croce svettano, in un cielo animato da nuvolette rosacee e azzurre, i quattro Viventi dell'Apocalisse: l'angelo per San Matteo, il bue per San Luca, il leone per San Marco e l'aquila per San Giovanni.

La facciata fu restaurata nel 1870 per volontà del cardinale titolare Lucien Bonaparte, nipote di Napoleone, conservando un fregio duecentesco e il portale cinquecentesco della facciata precedente. Il campanile in stile romanico fu voluto da Papa Innocenzo III all'inizio del XIII secolo.