Saints John and Paul were Roman soldiers who were Christians as well. They were martyred at Rome under Julian the Apostate c. A.D. 361-363 on the 26th of June, according to their Acta.
In the second half of the fourth century, Byzantius, the Roman senator, and Pammachius, his son, fashioned their house on the Cælian Hill into a Christian basilica.
In the fifth century the presbyteri tituli Byzantii (priests of the church of Byzantius) are mentioned in an inscription and among the signatures of the Roman Council of 499. The church was also called the titulus Pammachii after Byzantius’s son, the pious friend of St. Jerome. In the ancient apartments on the ground-floor of the house of Byzantius, which were still retained under the basilica, the tomb of two Roman martyrs, John and Paul, was the object of veneration as early as the fifth century.
The Sacramentarium Leonianum already indicates in the preface to the feast of the saints, that they rested within the city walls, while in one of the early itineraries to the tombs of the Roman martyrs (La Roma sotterranea), their grave is assigned to the church on the Cælian. The titulus Byzantii or Pammachii was consequently known at a very early date by the names of the two martyrs (titulus SS. Joannis et Pauli).
That the two saints are martyrs of the Roman Church, is historically certain; as to how and when their bodies found a resting-place in the house of Pammachius under the basilica, we only know that it certainly occurred in the fourth century. The year and circumstances of their martyrdom are likewise unknown. According to their Acts, which are of a purely legendary character and without historical foundation, the martyrs were eunuchs of Constantina, daughter of Constantine the Great, and became acquainted with a certain Gallicanus, who built a church in Ostia.
At the command of Julian the Apostate, they were beheaded secretly by Terentianus in their house on the Cælian, where their church was subsequently erected, and where they themselves were buried. The rooms on the ground-floor of the above-mentioned house of Pammachius were rediscovered under the Basilica of SS. Giovanni e Paolo in Rome. They are decorated with important and interesting frescoes, while the original tomb (confessio) of Sts. John and Paul is covered with paintings of which the martyrs are the subject. The rooms and the tomb form one of the most important early Christian memorials in Rome. Since the erection of the basilica, the two saints have been greatly venerated, and their names have been inserted in the Canon of the Mass. Their feast is kept on this day.