Fu costruita nel VI secolo e dedicata a san Teodoro di Amasea, sulle rovine degli Horrea Agrippiana, probabilmente riutilizzando un tempio circolare preesistente. La tradizione voleva che il tempio fosse dedicato a Romolo, e che qui fosse conservata la Lupa capitolina fino al 1471, prima di essere spostata al Laterano; un'ara antica è conservata e visibile nel cortile della chiesa[1].
Il mosaico dell'abside è anch'esso del VI secolo, e raffigura Cristo seduto su un orbe rappresentante i cieli, affiancato da Pietro e Paolo e dai martiri Teodoro (un'aggiunta dovuta al restauro di papa Nicola V) e Cleonico: Cristo indossa una veste nera con laticlavi d'oro, simboli di un elevato status nella società romana. Tradizionalmente la chiesa è considerata una delle sette diaconie originarie[2]: il primo diacono sarebbe stato assegnato da papa Agatone nel 678, mentre il primo diacono noto per nome è Roberto, intorno al 1073. La dedica ad un santo greco confermerebbe la costruzione della chiesa in un'epoca di influenza bizantina[3].
^Così la descrive Ridolfino Venuti, in Accurata e succinta descrizione topografica delle antichità di Roma, Volume 1, Roma 1763, p. 2: Vedesi da questa parte alle radici del Palatino un Tempietto dedicato a S. Teodoro dal volgo detto Santo Toto, di dove principieremo il nostro giro, che credo fosse prima dedicato a Romolo, dove forse furono esposti i due Fratelli [cioè, Romolo e Remo, abbandonati al Tevere, si credeva, lì presso], fabbricato fino dagli antichissimi tempi, e conservato sempre nel suo piccolo, e povero stato. Gli Antiquarj non fanno menzione di questo Tempietto, non l'avendo riguardato come antico: Ma se avessero letto Vittore, e Rufo, avrebbero veduto segnati da questi Autori due Tempj, uno situato nella IV Regione detta Via Sacra dedicato ai due Fratelli, l'altro nell'VIII detta del Foro Romano dedicato a Romolo. La tradizione, l'antlchità, l'esser nominato col nome di un S[anto]. Soldato, l'uso di portarvi i Bambini infermi, come anticamente, sono congetture, che fanno indubitabilmente credere essere stato il Tempio antico. Il Torrigio nella Istoria di questa Chiesa rapporta le varie opinioni intorno a chi dedicato fosse questo Tempio, risolvendo che la più approvata si è che fosse dedicato a Romolo da Tazio Re de' Sabini. Il Mosaico Cristiano pare molto antico, e del tempo di Felice IV. Stefano Infessura nel suo Diario dice, che essendo caduto da' fondamenti, Nicolò V lo risarcì, dopo d'avere acconciato il più antico, e soggiunge che lo rifece un poco più in là, ed un poco minor che non era [...]. In prova del Tempio Gentilesco non è lieve congettura la bella Ara che già era dentro il Tempio, e che da Clemente XI nell'ultimo risarcimento della Chiesa nel 1703 fu posta alla Porta: Inoltre in questa Chiesa fino al Secolo XVI vi era la Lupa di bronzo con i gemelli che ai tempi del Pancirolo, o poco prima era in Campidoglio stata portata.
^Ruolo supportato dalla collocazione del tempio - e poi della chiesa - nella sede di antichi depositi di grano, la cui amministrazione era passata dai funzionari imperiali ai funzionari ecclesiastici.
^Del resto il tratto della riva del Tevere tra il Ponte Sublicio e l'Isola Tiberina era detto Ripa Graeca, per le numerose presenze di comunità cristiane greche in fuga dall'Iconoclastia, riparate a Roma dall'VIII secolo. Analoga origine ebbe la vicina Basilica di Santa Maria in Cosmedin, ugualmente eretta in diaconia.