Im Liber Pontificalis wird der Bau der Basilika zwischen 468 und 483 Papst Simplicius zugeschrieben. Dieser widmete sie dem heiligen Diakon Stephanus und ließ sie auf einer ehemaligen Kaserne errichten, deren Reste man dazu vermutlich im 5. Jahrhundert abriss. Allerdings erhielt die Kirche ihre heutige Form erst im 12. Jahrhundert.
Zwischen 642 und 649 ließ Papst Theodorus I. die Reliquien der heiligen Primo und Feliciano aus den Katakomben an der Via Nomentana in den nordöstlichen Arm der Basilika in einer ihnen geweihte Kapelle unterbringen. Unter Papst Nikolaus V. (1447-1455) wurde die Betreuung der inzwischen verfallenen Kirche dem ungarischen Paulinerorden anvertraut. Dies geschah dank des Prokurators des Paulinerordens, Kapusi Bálint, der gute Beziehungen zum Papst unterhielt. So wurde der Hauptaltar unter anderem ungarischen Heiligen aus der königlichen Familie von Árpád gewidmet, nämlich dem Heiligen Stephan, dem ersten König von Ungarn, seinem Sohn, dem Heiligen Emeric, sowie König Ladislaus.
Schließlich wurde 1580 mit Unterstützung von Papst Gregor XIII. das Collegium Hungaricum gegründet, das bald darauf aus finanziellen Gründen mit dem Collegium Germanicum zusammengelegt wurde. Das päpstliche Collegium Germanicum et Hungaricum, das aus finanziellen Gründen mit dem Germanischen Kolleg zusammengelegt werden musste, um gute Priester auszubilden, die zur katholischen Gegenreformation beitragen sollten. Heute befindet sich das Päpstliche Deutsch-Ungarische Kolleg in der Nähe der Piazza Barberini und bereitet als europäisches Priesterseminar Studenten auf ihren diözesanen Dienst vor..