O imperador Constantino encomendou esta basílica no século IV dC, dando-lhe o nome de Basílica Apostolorum em homenagem aos apóstolos Pedro e Paulo, cujas relíquias sagradas foram guardadas aqui por cerca de cinquenta anos, desde as perseguições de Valeriano, no século III dC.
Só mais tarde o título foi mudado para igreja de São Sebastião, em homenagem ao soldado martirizado no tempo de Diocleciano, cujos restos mortais, guardados na catacumba adjacente, animaram cada vez com mais força o culto a este mártir.
Foi elevada a paróquia em 1714 pelo Papa Clemente XI, que a confiou aos cuidados dos monges cistercienses. Em 1826, o Papa Leão XII entregou-a aos padres da Ordem dos Frades Menores, que ainda hoje a gerem.
Finalmente, a 3 de maio de 1957, São Sebastião tornou-se protetor da polícia de trânsito de Itália graças à proclamação do Papa Pio XII. Ainda hoje, no dia 20 de janeiro, festa de São Sebastião, o Corpo de Polícia Municipal de Roma Capital celebra o santo com uma cerimónia solene.
