Construite dans la première moitié du IV siècle, au-dessus des catacombes du même nom, la basilique est dédiée à Sébastien, un martyr romain populaire du III siècle. Le terme « hors-les-murs » fait référence au fait qu'elle se trouve à l'extérieur du mur d'Aurélien, et la différencie de la basilique Saint-Sébastien située sur le Mont Palatin.
Selon une autre tradition, en 258, au cours des persécutions de Valérien, les catacombes ont été utilisées temporairement comme lieu de sépulture de deux autres saints martyrs de Rome, Pierre et 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 IX siècle.
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 I (858-867), tandis que l'autel du martyr est consacré par Honorius III, à la demande des Cisterciens à qui l'église est consacrée.
Au XIII siècle, l'arcade de la triple nef est murée.
L'édifice actuel est en grande partie du XVII siècle, la construction, commandée par le cardinal Scipione Borghese en 1609, est de Flaminio Ponzio et, après la mort de celui-ci en 1613, confiée à Vasanzio Giovanni.