In ancient times the catacombs were simply known with the name in catacumbas, a Greek term composed by two words, katà and kymbe, literally meaning "close to the cavity".

The underground graveyard, called di San Sebastiano since the Early Middle Ages, was known since the 3rd century as in memoria apostolorum, a toponym referred to the presence within the catacomb, for some time, of the relics of the Apostles Peter and Paul.

The Martyrologium Hieronymianum (5th century), at the same date, cites the recurrence of Peter in the Vatican, Paul on Via Ostiensis and utrumque in catacumbas, Tusco et Basso consulibus (during the consulship of Tuscus and Bassus, that is in 258).

The names of the martyrs are mentioned in a 7th-century catalogue, called Notula oleorum, while the Early Middle Ages itineraries for pilgrims do not cite Eutychius, because its sepulchre was hard to reach.

Nothing is known about Eutychius but his grave, discovered during excavations carried out in the 20th century in a crumbly area of the catacombs; a poem dedicated to him, by Pope Damasus I, is now displayed at the entry of the basilica.

[2] Thanks to the excavations carried out at the end of 19th and during the 20th century, it was possible to recreate the topographic and architectural history of the area - consisting of three levels of galleries - in which the catacombs lie.