Originalmente fue construida sobre el lugar en el que se alzaban los “horrea Agrippiana”, los almacenes de cereales y grano que Agripa mandó construir hacia el año 33 a.C. y que, sorprendentemente, permanecieron en funcionamiento hasta la Edad Media. También aquí se alzaba un antiguo santuario que señalaba la presencia de la famosa Lupercale, la gruta donde los gemelos Rómulo y Remo fueron amamantados por la loba.
La iglesia fue dedicada a san Teodoro de Amasea, un legionario romano martirizado en Oriente en los años de las persecuciones del emperador Maximiano, cuyas reliquias se siguen conservando en su interior. Tras varias remodelaciones a lo largo de los siglos, la iglesia fue confiada a la Archicofradía del Sagrado Corazón de Jesús, fundada en 1729 con el objetivo de reprimir la blasfemia y de promover el culto al Sagrado Corazón de Jesús.
En el año 2004 san Juan Pablo II concedió finalmente el uso de la iglesia al Patriarca de Constantinopla y a la comunidad greco-ortodoxa romana.