Christian tradition also has Paul being behead in Rome around the mid 60s A.D. during the reign of Nero. Most Bible dictionaries and some commentaries can give us details on the traditions surrounding Paul's death.
"Concerning the time, place, and manner of his death, we have little certainty. It is commonly believed that, when a general persecution was raised against the Christians by Nero, about A.D. 64, under pretence that they had set Rome on fire, both St. Paul and St. Peter then sealed the truth with their blood; the latter being crucified with his head downward; the former being beheaded, either in A.D. 64 or 65, and buried in the Via Ostiensis. EUSEBIUS, Hist, Eccles. lib. ii. cap. 25, intimates that the tombs of these two apostles, with their inscriptions, were extant in his time; and quotes as his authority a holy man of the name of Caius, who wrote against the sect of the Cataphrygians, who has asserted this, as from his personal knowledge. See Eusebius, by Reading, vol. i. p. 83; and see Dr. Lardner, in his life of this apostle, who examines this account with his usual perspicuity and candor.
"Other writers have been more particular concerning his death: they say that it was not by the command of Nero that he was martyred, but by that of the prefects of the city, Nero being then absent; that he was beheaded at Aquae Salviae, about three miles from Rome, on February 22; that he could not be crucified, as Peter was, because he was a freeman of the city of Rome.
"But there is great uncertainty on these subjects, so that we cannot positively rely on any account that even the ancients have transmitted to us concerning the death of this apostle; and much less on the accounts given by the moderns; and least of all on those which are to be found in the Martyrologists. Whether Paul ever returned after this to Rome has not yet been satisfactorily proved. It is probable that he did, and suffered death there, as stated above; but still we have no certainty" (Commentary on the Bible by Adam Clarke, commenting on Acts 28:31).