No Liber Pontificalis, a construção da basílica é atribuída ao testamento do Papa Simplício entre 468 e 483, que a dedicou a Santo Stefano e a mandou construir sobre um antigo quartel. Este foi destruído e nivelado para a construção da basílica provavelmente no século V.
Somente no século XII a igreja assumiu sua forma atual.
Além disso, entre 642 e 649, o Papa Teodoro I transferiu as relíquias dos santos Primo e Feliciano das catacumbas da Via Nomentana, no braço nordeste da basílica, para uma capela dedicada a eles.
Com o Papa Nicolau V (1447-1455), o cuidado da igreja, agora em ruínas, foi confiado à ordem paulina húngara, graças ao procurador da ordem paulina, Kapusi Bálint, que mantinha boas relações com o próprio Papa. Foi assim que o altar-mor foi dedicado, entre outros, aos santos húngaros da família real dos Árpád, como Santo Estêvão, primeiro rei da Hungria, seu filho São Emerico e o rei Ladislau.
Finalmente, em 1580, com o apoio do Papa Gregório XIII, foi fundado o Collegium Hungaricum, que por razões financeiras teve que se unir ao Colégio Germânico, para formar bons padres que contribuíssem para a contra-reforma católica.