Cesarz Konstantyn zlecił budowę tej bazyliki w IV wieku naszej ery, nadając jej nazwę Basilica Apostolorum (Bazylika Apostołów) ku czci Apostołów św. Piotra i św. Pawła, których święte relikwie były tu przechowywane przez około pięćdziesiąt lat, począwszy od prześladowań Waleriana w III wieku naszej ery.
Dopiero później świątyni nadano nową nazwę, poświęcając ją św. Sebastianowi, w celu upamiętnienia żołnierza zabitego, za czasów Dioklecjana, śmiercią męczeńską. Jego szczątki, przechowywane w pobliskich katakumbach, z coraz większą siłą ożywiały kult oddawany jego pamięci.
Kościół został erygowany w roku 1714 przez papieża Klemensa XI i został powierzony opiece Ojców Cystersów. W 1826 roku papież Leon XII przekazał go kapłanom Zakonu Braci Mniejszych, którzy do dziś strzegą murów świątyni.
Dnia 3 maja 1957 r. Św. Sebastian został patronem włoskiej policji drogowej, dzięki dekretowi wydanemu przez papieża Piusa XII. Do dzisiaj, 20 stycznia każdego roku, w święto św. Sebastiana, Korpus Policji Miejskiej Stolicy Rzymu bierze udział w uroczystych obchodach ku czci świętego.
