Fu eretta a partire dal 398 dal senatore Bizante o da suo figlio Pammachio sul sito di un edificio, databile tra il I e il II secolo, utilizzato prima come domus ecclesiae da una comunità cristiana e poi divenuta sepoltura dei martiri Giovanni e Paolo.

La chiesa originaria fu danneggiata dai Visigoti di Alarico I durante il sacco di Roma (410), poi da un terremoto nel 442 e venne infine saccheggiata dai Normanni nel 1084. Il Papa Pasquale II (1099 - 1118) ne promosse i lavori di restauro, vi aggiunse il campanile e il portico, che sostituì l'originario nartece. L'edificio fu continuamente rimaneggiato nei secoli successivi; in particolare furono notevoli gli interventi promossi nel 1715 dal cardinale Fabrizio Paolucci. Ha assunto l'attuale fisionomia nel 1951, quando il cardinale Francis Joseph Spellman ne ha fatto ripristinare la facciata paleocristiana.

La navata è lunga 44,30 metri ed ampia 14,68, con navatelle larghe 7,40. La separazione tra le navate era effettuata tramite dodici colonne che reggevano tredici archi. In quel periodo venne aggiunta l'abside con quattro grandi finestre e vennero tamponate le finestre delle navatelle; al posto di esse ne vennero aperte tredici più altrettanti oculi nel cleristorio; la navata centrale assumeva quindi un aspetto slanciato e luminoso. La facciata era caratterizzata da una serie di arcate sormontate in alto da cinque finestre. I resti della decorazione a mosaico, dell'affresco e dello stucco dell'abisde e della zona oltre le arcate si trovano in un piccolo museo della basilica.