La chiesa di san Teodoro sorgeva fuori dalle mura cittadine sul lungomare che conduceva a Ponente attraverso una via di collegamento, piuttosto impervia, stretta da grossi scogli e dalla collina, da cui scendevano piccoli torrenti. Consacrata nel 1100, la chiesa fu affidata ai Canonici Mortariensi che officiarono fino al XV secolo quando furono sostituiti dai Canonici Lateranensi.
Fu amata dalle famiglie nobili genovesi che contribuirono alla realizzazione delle decorazioni, in particolare dai Lomellini che nel 1303 fecero erigere all’interno dell’edificio una cappella dedicata a San Sebastiano e commissionarono per adornala, all’inizio del ‘500, a Filippino Lippi una pala con il Martirio del Santo, oggi conservato a Palazzo Bianco.
I Canonici Lateranensi rimasero fino al 1797 quando furono costretti ad abbandonarla a causa della soppressione degli ordini religiosi; l’Abbazia venne spogliata dal governo napoleonico che trasferì in Francia molte opere d’arte, tra cui il dipinto di Filippino Lippi raffigurante il “Martirio di San Sebastiano”, restituito solo anni dopo alla città di Genova.
La posizione dell’edificio, su una scogliera a picco sul mare lo rese soggetto alle mareggiate che talvolta ne compromisero la stabilità, così nel 1596, e nel Natale del 1821.
Nel  1870 l’antica chiesa romanica di San Teodoro venne abbattuta, per ragioni di viabilità cittadina (l’apertura dell’attuale via Milano) e per l’ampliamento del porto.