Veduta Marulićeve ulice prema jugu gledano od ulice Pod voltom, vidi se i crkva sv. Sebastijana
Prvotna crkva na njenu mjestu podignuta je prema predaji 1291. godine kao zavjet u vrijeme kuge. Stari grad je u to doba bio okružen bedemima i kulama, kuće su se gradile u uskim ulicama, tzv. kalama koje su sukcesivno trasirane u ranom srednjem vijeku na ruševinama rimskog kastruma Tarsatike, nekoć ključne točke u obrambenom sustavu "liburnijskog limesa". U jednoj od tih kala smještena je crkva sv. Sebastijana.
U notarskim spisima iz 15. stoljeća često je riječ o "kontradi" i crkvi sv. Sebastijana. Nad ulaznim vratima uklesan je memorijalni natpis iz kojega se razaznaje da je u doba gastalda Ivana Dotića 1562. sagrađena "u slavu Boga i božanskog Sebastijana" (ad laudem Dei divique Sebastiani fraternitas fieri fecit tempore Joannis Dotich Castaldi 1562). Gastaldi sv. Sebastijana bili su ugledni riječki patriciji iz obitelji Franković, Gladić i Stemberger. U nekoliko je navrata bilo pokušaja da se crkvica sruši, što su građani spriječili jer su uz nju bile vezane tradicionalne svečanosti i procesije. Nakon otklanjanja ruševine iza začelja te crkve otkriven je kasnoantički zid iz 4. st., sekundarno uzidan u sakristiju i zaključak svetišta. Posljednji put crkva sv. Sebastijana obnovljena je 1885., kada je po projektu G. Paulinicha, inspiriranog pročeljem Zborne crkve, bila generalno obnovljena i dobila današnji izgled. Crkva je uređena i prebojana 1986. godine.
