Die Kirche steht auf dem Caelius, einem der sieben Hügel Roms. Wie bei so viele Bauten in der ewigen Stadt, umfasst auch die Geschichte von Santo Stefano Rotondo mehr als nur ein Jahrtausend. Bereits zwischen 468 und 483 wurde die Kirche auf den Überresten eines noch älteren Vorgängerbaus errichtet. Wie Grabungen während der jüngsten Renovierung gezeigt haben, war auch schon der Vorgängerbau eine Kirche, die in konstantinischer Zeit, also während der Herrschaft Kaiser Konstantin des Großen, im 4. nachchristlichen Jahrhundert errichtet worden war.
Santo Stefano Rotondo ist, wie der Name schon sagt, eine Rundkirche und orientiert sich vermutlich an der Grabeskirche in Jerusalem. Errichtet worden ist sie aus den typischen antiken Ziegelsteinen, die flacher und breiter als diejenigen sind, die aus der deutschen Backsteingotik bekannt sind.
Usprünglich bestand die Kirche aus einem runden Zentralraum. Um den Zentralraum waren drei konzentrische Umgänge errichtet. Der Zentralraum und die Umgänge waren durch 22 ionische Säulen getrennt. Über den Säulen wurde ein Tambour mit 22 Metern Durchmesser und 22 Metern Höhe errichtet. In ihm befanden sich 22 Fensteröffnungen, die allerdings während des letzten Umbaus in der Renaissance zumeist zugemauert wurden. Der äußerste Umgang ist später abgerissen worden. 1130 wurden im Innenraum noch drei Bögen eingefügt um den Tambour zu stützen.
Im Mittelalter verfiel die Kirche zunehmend. Ein Beobachter aus dem 15. Jahrhundert lobt die marmornen Säulen und die Cosmaten-Arbeiten, erwähnte aber auch das ‚unglücklicherweise fehlende Dach’.
1454 übergab Papst Nikolaus V. die Kirche dem in Ungarn gegründeten Orden der Pauliner, woraufhin die Kirche später zu inoffiziellen Kirche der Ungarn in Rom wurde. In der Zeit erfolgte auch der letzte Umbau, vielleicht sogar unter Beteiligung von Giovanni Baptista Alberti. Als die Jesuiten die Kirche übernahmen, wurde ein ungarisches Priesterseminar eingerichtet, welches mit einem deutschen Seminar fusioniert wurde, als während der türkischen Besetzung Ungarns nur wenige Ungarn nach Rom gelangten. Das Collegium Germanicum et Hungaricum befindet sich noch heute in der Nähe der Kirche, auch wenn die Jesuiten zwischenzeitlich aufgelöst waren.
Beinahe alle Mosaiken aus der Frühzeit der Kirche sind zerstört worden. In der Kapelle der Heiligen Primo und Feliciono finden sich noch Reste von Mosaiken aus dem 7. Jahrhundert. Auch in der Apsis der Kirche sind noch Mosaiken aus dieser Zeit erhalten. Sie zeigen unter anderem die beiden Heiligen. Die Überführung der Gebeine von Primo und Feliciano gilt als früheste Überführung von Märtyrer-Reliquien in eine Kirche.
In der Kirche finden sich auch noch 34 Wandgemälde aus dem 16. Jahrhundert, die oft sehr drastische Martyriumsszenen zeigen. Auch der Hochaltar wurde im Stil der italienischen Renaissance errichtet und stammt aus dem ausgehenden 15. Jahrhundert.
Die Kirche ist dem Erzmärtyrer Stephanus geweiht, dessen Gebeine kurz vor Errichtung der Kirche in Jerusalem gefunden und nach Rom gebracht worden waren. In der Kirche findet sich auch eine kleine Kapelle, die dem hl. Stefan geweiht ist, dem ersten und heilig gesprochenen König der Ungarn.
Unter der Kirche sind bei Ausgrabungen Reste eines sogenannten Mithräums gefunden worden. Der Mithras-Kult stammt aus Syrien und stand zu Beginn des ersten Jahrtausends durchaus in Konkurrenz zum Christentum. Der Kult wurde vor allem von Soldaten betrieben. Somit passt das Mithräum zu den Überresten einer römischen Kaserne, die in der Nähe auf dem Caelius gefunden wurden. Das Mithräum von Santo Stephano ist nicht das einzige welches in Rom unter einer Kirche gefunden wurde. Auch unter St. Clemente wurde ein solche Versammlungsstätte des Mithras-Kultes ausgegraben.
