San Teodoro church stood outside the city walls on the waterfront that led towards the west through a rather impervious connecting road,  pressed by large rocks and the hill, from which small streams descended. Consecrated in 1100, the church was entrusted to the Mortariense Canons who officiated there until the fifteenth century when they were replaced by the Lateran Canons.

This church was loved by the Genoese noble families, in particular by the Lomellini family, who contributed to the realization of its decorations. In 1303 they erected a chapel dedicated to Saint Sebastian inside the building and commissioned, at the beginning of the 16th century, to Filippino Lippi an altarpiece with the Martyrdom of the Saint, that is now preserved in Palazzo Bianco.

The Lateran Canons remained until 1797 when they were forced to abandon it due to the suppression of religious orders; the Abbey was burgled by the Napoleonic government that moved many piece of art to France, including the painting by Filippino Lippi depicting the "Martyrdom of Saint Sebastian", which returned only years later to the city of Genoa.

The position of the building, on a cliff overlooking the sea, made it subject to storm surges which sometimes compromised its stability, as happened in 1596, and in the Christmas of 1821.

In 1870 the ancient Romanesque church of San Teodoro was demolished, for reasons of city traffic (the opening of the current via Milano) and for the expansion of the port.