W Liber Pontificalis budowa bazyliki jest przypisana woli papieża Symplicjusza, a jej budowę datuje się na lata: 468 - 483. Została poświęcona przez św. Stefana, który nakazał, by świątynie wzniesiono na miejscu starożytnych koszar, które następnie zniszczono, a teren wyrównano pod budowę kościoła, prawdopodobnie w V wieku.
Dopiero w XII wieku kościół nabrał obecnego kształtu.
Ponadto między 642 a 649 papież Teodor I kazał przenieść relikwie świętych Prymusa i Felicjana z katakumb przy Via Nomentana leżących w północno-wschodnim ramieniu bazyliki, do poświęconej im kaplicy.
Za czasów papieża Mikołaja V (1447-1455) opiekę nad kościołem, który wtedy znajdował się w opłakanym stanie, powierzono węgierskiemu Zakonowi Paulinów, za sprawą prokuratora Ojców Paulinów, Kapusi Bálinta, który miał dobre stosunki z samym papieżem. Ołtarz główny został poświęcony m.in. węgierskim świętym z rodziny królewskiej Arpadów, św. Stefanowi pierwszemu królowi Węgier oraz jego synowi św. Emerykowi i królowi Władysławowi.
Ostatecznie w 1580 r. dzięki poparciu papieża Grzegorza XIII powstało Collegium Hungaricum, które ze względów finansowych musiało zostać połączone z Collegium Germanicum, aby kształcić dobrych księży, którzy przyczyniliby się do katolickiej kontrreformacji.