Il sito originariamente denominato "ad catacumbas" ossia, secondo la spiegazione più diffusa, "presso l'avvallamento", per la presenza di antiche cave di pozzolana.
Per consuetudine questo toponimo è stato poi assunto per indicare i cimiteri sotterranei cristiani, noti oggi come catacombe.
Come spesso accadeva nell'antichità la cava venne riadattata e adibita dai cristiani in cimitero, con sepolture modeste come loculi e arcosoli. La comunità cristiana, dato l'ingente numero dei propri membri, il processo dell'inumazione e l'elevato costo dei terreni suburbani, continuò l'escavazione della catacomba fino a formare una districata rete di gallerie sotterranee di 12 km su tre livelli.

Prima dell'avvento del cristianesimo i romani usavano chiamare i loro luoghi di sepoltura con il vocabolo greco "necropolis", cioè la città dei morti.
I primi cristiani, invece, preferirono denominarlo "cimitero", dal greco "koimào" che significa "dormire".

Percorrendo le gallerie della catacomba si può notare la grande varietà delle tombe e delle decorazioni. Ogni tomba aveva il suo piccolo contrassegno per essere riconosciuta, spesso un oggetto o un semplice frammento: una lucerna, una moneta, un fondo di coppa, un monile, un giocattolo di un bambino.
In molti casi, un nome tracciato o un graffito sulla calce di chiusura, ci ha tramandato la memoria del defunto.
un evento fondamentale per lo sviluppo e la notorietà della catacomba fu la deposizione del corpo del martire Sebastiano.
La venerazione dei fedeli per questo testimone di Dio provocò mutamenti profondi all'interno della catacomba. I posti vicini alla tomba venerata vennero sempre più ricercati. 

---

Attorno alla metà del III d.c. secolo la topografia del luogo fu letteralmente sconvolta.
"La piazzola" fu totalmente interrata con una colmata di terra e si creò un nuovo grande spazio in piano ad un livello superiore rispetto a quello dei mausolei. In questa fase fu creata la "triclia" che era un ambiente coperto, alla quale si accedeva da una piccola scala e formato da una grande sala porticata, dotata di un bancale addossato alla parete di fondo.
Molti studiosi ritengono che, proprio in questo periodo, il complesso ospitasse temporaneamente le spoglie dei S.S. Apostoli e martiri Pietro e Paolo e che le loro spoglie si trovassero all'interno di questo piccolo monumento. Inoltre, in questo luogo, sul muro di fondo della triclia, sono stati rinvenuti moltissimi graffiti con invocazioni e preghiere rivolti a Pietro e Paolo, testimonianze del profondo culto congiunto dei due santi in questo sito, denominato "Memoria Apostolorum".
Alcuni di questi graffiti sono ancora visibili e particolarmente interessanti e suggestivi, come quello di un certo pellegrino che scrisse: "Paule et Petre petite pro Victore", una richiesta di intercessione rivolta ai due martiri più importanti di tutta la cristianità.