The following is a reply by Hieromonk Job (Gumerov) to a question about why the Feast of Saints Peter and Paul is held today, which I have translated from Russian and hyperlinked:
According to Church tradition, Saints Peter and Paul, the first among the Apostles, accepted holy martyrdom on the same day: June 29 (July 12 [on the civil calendar]). This date is indicated in ancient calendars (fourth-century Roman and fifth-century Carthaginian), in the martyriology of the Blessed Jerome (fourth century), and in the Sacramentarium of Pope Gregory the Great (sixth century).
Scholars believe that the Holy Apostle Peter arrived in Rome in the year 67. Here he converted many people to Christ. In Rome he wrote the Second Catholic Epistle to Christians who had converted from Judaism and Paganism and found themselves in Asia Minor. The Lord forewarned him of his imminent departure from this earthly life: shortly I must put off this my tabernacle, even as our Lord Jesus Christ hath shewed me. Moreover I will endeavour that ye may be able after my decease to have these things always in remembrance (2 Peter 1:14-15). The Apostle Peter's disciples convinced him to flee at the beginning of the persecution of the Church by the Emperor Nero, so as not to be deprived of their pastor. Peter agreed out of love for Christ. Leaving the city, the Apostle encountered Christ on the ancient Appian Way. To his question, "Where are you going, Lord?", the Saviour answered, "I go to Rome, to be crucified anew." On this place there is now a church (Domine Quo Vaids) in which there is a copy of the stone on which the Lord's footprints are impressed. The original stone with the Lord's footprint is in the Church of St Sebastian in Rome. After his return to Rome, the Holy Apostle Peter was imprisoned in the Mamertino Prison (Carcere Mamertino), which is on the slope of the Capitoline Hill below the Church of St Joseph the Betrothed (San Giuseppe). From the Mamertino Prison the Apostle Peter was brought to Vatican Hill, on the right bank of the Tiber. The Circus of Nero was located on that hill. Here the Apostle received his martyric death. Here were fulfilled the Lord's words: When thou wast young, thou girdest thyself, and walkedst whither thou wouldest: but when thou shalt be old, thou shalt stretch forth thy hands, and another shall gird thee, and carry thee whither thou wouldest not. This spake He, signifying by what death he should glorify God. And when he Had spoken this, he saith unto him, Follow Me (Jn 21: 18-19). Like his Teacher, the Apostle was raised onto a cross, but out of humility asked to be crucified upside down. He was buried on this very Vatican Hill by the Holy Hieromartyr Clement of Rome and other disciples. The Roman Christians piously preserved the memory of this place. When in 1941 excavations were undertaken under the foundations of St Peter's Basillica a plate was found in this very place with the brief but expressive inscription in Greek: "Peter is here."
We do not know when the Apostle Paul was in Rome. As with the Apostle Peter, the Lord revealed the time of death to his chosen vessel (Acts 9:15): I am now ready to be offered, and the time of my departure is at hand. I have fought a good fight, I have finished my course, I have kept the faith: Henceforth there is laid up for me a crown of righteousness, which the Lord, the righteous judge, shall give me at that day: and not to me only, but unto all them also that love His appearing (2 Tim 4: 6-8). Christians preserved the pious memory of the place where the Apostles parted ways; a church dedicated to both Apostles stands in this place on the Via Ostiense. The Apostle Paul was brought to the outskirts of the city known as the Aquae Salviae. As a Roman citizen, he could not be crucified. Here he was beheaded. The majority of scholars date the Holy Apostles' martyrdom to 67 AD.
Saint Constantine, the Equal-to-the-Apostles, built a church over the grave of the Apostle Paul in 324.