Die Abbildung der Strukturen der Basilika von S. Sebastiano ad Catacumbas zeigt, daß deren Entstehung - nicht nur dem Kognomen nach - eindeutig in einem zömeterialen Kontext zu sehen ist. Unterhalb der Substrukturen der Basilika befinden sich die Gänge der Katakombe; erkannbar an den gestrichelten Linien. Ebenfalls deutlich erscheinen die Grundrisse einer ganzen Reihe verschiedener Mausoleen an der Basilika selbst und in deren unmittelbarem Umfeld.

Während der Verfolgungen unter Valerian wurden - der Überlieferung folgend - im Jahre 258 die Reliquien der Apostel Petrus und Paulus zeitweise an diesen Ort gebracht. Obgleich in der Forschung umstritten, konstituierte dies eine Tradition der Apostelverehrung, die auch noch Jahrhunderte später, lange nachdem die Reliquien der Apostel wieder an die ursprünglichen Ruheplätze gebracht worden waren (4. Jhd.), nachzuweisen ist. Als Folge dieser lokalen Apostelverehrung entstand ein Tropaion, das in den Quellen für das Jahr 258 erschien.

Während des vierten Jahrhunderts entstand an diesem Ort eine große Zömeterialbasilika, die das Tropaion ersetzte und der Verehrung der Apostel diente. Demzufolge wurde die Basilika als Wohnung der Heiligen bezeichnet und aus dieser widmung ging das spätere Apostelpatrozinium hervor, das im späten vierten Jahrhundert nachweisbar ist. Da sich auch die Reliquien des h. Sebastian an diesem Ort befanden, begann sein Kult die Erinnerung an die Präsenz der Apostelreliquien zu überlagern. Aber erst in der Zeit um 638-642 ist ein Sebastianpatrozinium im Zusammenhang mit der Basilika nachweisbar.