Built originally in the first half of the 4th century, the basilica is dedicated to St. Sebastian, a popular Roman martyr of the 3rd century. The name ad catacumbas refers to the catacombs of St Sebastian, over which the church was built, while "fuori le mura" refers to the fact that the church is built outside the Aurelian Walls, and is used to differentiate the basilica from the church of San Sebastiano al Palatino on the Palatine Hill.
According to the founding tradition, in 258, during the Valerian persecutions, the catacombs were temporarily used as place of sepulture of two other saints martyred in Rome, Peter and Paul, whose remains were later transferred to the two basilicas carrying their names: whence the original dedication of the church, Basilica Apostolorum ("Basilica of the Apostles"). The dedication to Sebastian dates to the 9th century.
Sebastian's remains were moved here around 350. They were transferred to St. Peter's in 826, fearing a Saracen assault: the latter, in fact, materialized, and the church was destroyed. The building was refounded under Pope Nicholas I (858–867), while the martyr's altar was reconsecrated by Honorius III (1216–1227), by request of the Cistercians, who had received the place. In the 13th century the arcade of the triple nave was walled in.
S. Sebastiano is one of the seven basilicas travellers to Rome traditionally visited, especially after 1553 when St. Philip Neri, initiated the Seven Churches Visitation, a special pilgrimage done in one day starting from St. Peter's Basilica and ending at the Basilica di Santa Maria Maggiore. The street which links Basilica of Saint Paul Outside the Walls with S. Sebastiano is still called "Via delle Sette Chiese".
The current edifice is largely a 17th-century construction, commissioned by Cardinal Scipione Borghese in 1609 from Flaminio Ponzio and, after Ponzio's death in 1613, entrusted to Giovanni Vasanzio, who completed it.