La chiesa paleocristiana, dedicata al diacono e primo martire Santo Stefano, è situata sul Celio, uno dei più alti tra i sette leggendari colli di Roma. La soluzione architettonica della chiesa, con i suoi tre cerchi concentrici e la forma a croce greca, la fa assomigliare alla basilica del Santo Sepolcro di Gerusalemme. Proprio considerando la forma così particolare della chiesa, già nel X secolo si era pensato che essa in origine fosse il tempio della divinità pagana Faunus o dell’imperatore Claudio, e che nei primi tempi della cristianità fosse stata dedicata al primo martire, analogamente al più conosciuto, e anch’esso rotondo, Pantheon.

Secondo la testimonianza del Liber Pontificalis, la basilica fu costruita su ordine di papa Simplicio (468-483). La costruzione antica era ornata con mosaici e marmo. Purtroppo le decorazioni originali sono andate completamente perdute. San Gregorio Magno (papa dal 590 al 604) vi tenne alcune prediche. Nel VII secolo le ossa dei santi martiri romani Primo e Feliciano furono traslate nella chiesa dalle catacombe di via Nomentana. Nell’anello esterno della chiesa fu eretta per i due martiri una splendida cappella, che nel Medioevo era un luogo importante per i pellegrini. Nell’alto Medioevo la chiesa, che era parzialmente in rovina, fu ampiamente ristrutturata e architettonicamente modificata.

Nel 1613 sull'altare venne collocato un alto tabernacolo di legno intagliato, oggi nell'ambulacro. La chiesa venne quindi affidata all'ordine paolino che la mantenne fino al 1580, quando papa Gregorio XIII la affidò al "Collegium hungaricum", poi a sua volta unificato al "Collegium germanicum", un convitto retto dai gesuiti destinato ai sacerdoti di lingua tedesca. Nello stesso anno venne realizzata la nuova porta della sacrestia e intorno all'altare venne costruito un recinto ottagonale, decorato con sculture (stemmi papali) e affreschi di Niccolò Circignani, detto il Pomarancio. Il recinto è decorato con 24 scene che imitano rilievi scultorei, in toni di giallo, raffiguranti la storia di santo Stefano e del suo culto, in particolare, in Ungheria (vedi in particolare la scena del sogno di Sarota, madre di santo Stefano d'Ungheria).

Nel 1583 lo stesso Pomarancio ricevette l'incarico di affrescare il muro che chiudeva l'ambulacro con scene di martirio. Il ciclo inizia con la Strage degli innocenti, continuando con la Crocifissione di Gesù, a cui segue il martirio di santo Stefano, con sullo sfondo le raffigurazioni dei supplizi degli Apostoli. I dipinti sono forniti di didascalie in latino e in italiano. Alcune delle scene, in cattivo stato di conservazione, vennero malamente ridipinte nel XIX secolo.