Si trova al terzo miglio della Via Appia Antica, al di fuori delle mura aureliane per questo viene detta "fuori le mura" anche per distinguerla dalla chiesa di San Sebastiano al Palatino.
Eretta originariamente nella prima metà del IV secolo sul luogo dove nel 258 furono temporaneamente trasportati i corpi dei santi Pietro e Paolo, la chiesa, che fa parte delle sette “Basiliche Giubilari”, fu intitolata a San Sebastiano, un martire romano del III secolo, le cui reliquie avevano trovato sistemazione nella sottostante cripta.
Distrutta dopo un assalto dei Saraceni, i resti di san Sebastiano vennero rimossi e trasferiti a San Pietro in Vaticano. Furono riportati solo nel 1218 da papa Onorio III dopo la riedificazione della chiesa voluta da papa Nicola I.
L'edificio che è visibile oggi risale alla ricostruzione avvenuta sotto il cardinale Scipione Borghese nipote di papa Paolo V. I lavori, iniziati nel 1608, furono affidati a Flaminio Ponzio prima e in secondo tempo a Giovanni Vasanzio autore della facciata terminata nel 1613.
L’elegante facciata di Giovanni Vasanzio è costituita, nell’ordine inferiore, da un portico a tre archi sorretti da colonne ioniche di granito, a cui corrispondo, nell’ordine superiore, tre grandi finestre separata da paraste.
L'interno è a navata unica, con un bel soffitto ligneo intagliato del Vasanzio con stemmi del cardinale Borghese e di papa Gregorio XVI che nel XIX secolo promosse il restauro dell’edificio.
Sul lato destro si trova la cappella delle reliquie, decorata nel 1625, in cui è conservata l’originale pietra con le impronte di Cristo del Domine quo vadis?, una delle frecce che martirizzarono san Sebastiano e parte della colonna alla quale il santo fu legato durante il martirio.
Sempre sul lato destro vi è la Cappella Albani, costruita nel 1716 su commissione di papa Clemente XI da Carlo Maratta, Alessandro Specchi, Filippo Barigioni e Carlo Fontana. A pianta quadrata con abside e cupola è decorata con opere di Pier Leone Ghezzi e Giuseppe Passeri.
Sul lato sinistro, in corrispondenza della sottostante cripta, si trova la Cappella di San Sebastiano, progettata da Ciro Ferri nel 1672. Qui si trova una statua giacente di San Sebastiano capolavoro di Giuseppe Giorgetti, allievo del Bernini.
Tra la cappella delle Reliquie e la cappella Albani, si apre la scala che porta alle catacombe di San Sebastiano.