The origins of the catacomb may be traced to the third century, when a series of galleries were dug out from a flat entrance on the Parioli hillside.

The catacomb, which takes its name after the alleged martyr buried within it, underwent several structural changes during the fourth century; some of the modifications occurred above the ground, where a three-nave basilica with a crypt was built, others took place in underground with the excavation of two further galleries. The current state of conservation of the monument  only permits access to the middle floor.

In the eight century, a small room was opened just behind the entrance. It was dedicated to the cult of St Valentine, and its walls were decorated with a pictorial representation of  the Crucifixion, the Virgin with the Child, along with a few figures portraying saints.