Selon une autre tradition[2], en 258, au cours des persécutions de Valérien, les catacombes ont été utilisées temporairement comme lieu de sépulture des deux autres saints martyrs de Rome, les apôtres saint Pierre et saint Paul, dont les restes ont été transférés plus tard dans les deux basiliques portant leurs noms : d’où la dédicace originelle de l’église, Basilica Apostolorum (« Basilique des Apôtres »). La dédicace de Sébastien remonte au IXe siècle[3].
Les reliques de Sébastien sont placées dans l’église autour de 350. Elles sont transférées à Saint-Pierre en 826, juste avant une attaque sarrasine au cours de laquelle l’église est détruite. Le bâtiment est reconstruit sous le pontificat de Nicolas Ier (858-867), tandis que l’autel du martyr est consacré par Honorius III, à la demande des Cisterciens à qui l’église est consacrée.
La sculpture de Saint Sébastien sur l'autel, dans la première chapelle à gauche, est d'Antonio Giorgetti(en).
La chapelle des reliques abrite une pierre portant les traces présumées de pas de Jésus, liées à l'épisode de Quo vadis des apocryphes de Pierre, et une des flèches qui ont frappé saint Sébastien avec une partie de la colonne à laquelle il a été lié au cours de son martyre.