Kościół już od roku 258 obchodził święto obu apostołów św. Piotra i św. Pawła razem w dniu 29 czerwca, zarówno na Zachodzie, jak i na Wschodzie. Połączono św. Pawła wraz ze św. Piotrem w liturgicznym świętowaniu w jednym dniu nie dlatego, aby równać go w prymacie z pierwszym następcą Chrystusa. Chodziło o podkreślenie, że obaj apostołowie byli współzałożycielami gminy chrześcijańskiej w Rzymie, że obaj w tym mieście oddali dla Chrystusa życie swoje oraz że w Rzymie są ich relikwie.
Św. Piotr, według podania, poniósł śmierć męczeńską na wzgórzu watykańskim w 64 roku . Miał być ukrzyżowany, według świadectwa Orygenesa, głową na dół na własną prośbę, gdyż czuł się niegodnym umierać na krzyżu jak Chrystus. Cesarz Konstantyn Wielki wystawił ku czci św. Piotra nad jego grobem bazylikę. Obecna Bazylika św. Piotra, zbudowana została w latach 1506-1629.
Św. Paweł poniósł śmierć męczeńską w Rzymie ok. 67 roku. Wcześniej został aresztowany w Jerozolimie w 60 r. Przebywał w więzieniu w Cezarei Palestyńskiej ponad dwa lata, głosząc i tam Chrystusa. W Rzymie także spędził jakiś czas jako więzień, aż z powodu braku dowodów winy został wypuszczony na wolność. Ze swojego więzienia w Rzymie Paweł wysłał szereg listów do poszczególnych gmin i osób. Po wypuszczeniu na wolność zapewne udał się do Hiszpanii (Rz15, 24-25), a stamtąd powrócił do Achai. Według bardzo starożytnego podania, św. Paweł miał ponieść śmierć od miecza. Nie jest znany dzień jego śmierci. Za to dobrze zachowano w pamięci miejsce jego męczeństwa – Aquae Salviae za Bramą Ostyjską w Rzymie. Po edykcie cesarza Konstantyna Wielkiego (313 r.) ciało św. Piotra przeniesiono do Watykanu, a ciało św. Pawła na miejsce jego męczeństwa, gdzie cesarz wystawił ku jego czci bazylikę pod wezwaniem św. Pawła.