There are major problems with proving that Peter or Paul ever lived in or visited Rome in the first century AD. Contemporary non-Christian writings never mention their being in Rome. Even more troubling, contemporary Christian writings also do not mention their presence. "After the fact" Christian sources from the period immediately following the time of Peter and Paul aren't a lot more helpful: they all require some "interpretation" to place either Peter or Paul in Rome. Not one of the early writers ever says specifically that they were in Rome.

Nonetheless, by the middle of the second century there was a strong tradition among the already growing Christian population in Rome that both Peter and Paul had lived for a time and then died as martyrs in the city. Peter, the leader of the Christian apostles, had come to Rome, according to this tradition, to gain converts for the new religion. Paul, a former persecutor of Christians (it was said that he actually participated in the martyrdom of Saint Stephen) had miraculously been converted on the road to Damascus and was eventually accused of sedition. Paul had previously acquired Roman citizenship and demanded a trial in Rome. Both Peter and Paul were said to have died in the first persecution of Christians, the one that was launched by Nero when he needed a scapegoat for the fire that leveled most of Rome in 64 AD.

The Christian community in Rome was an easy target. They were a small but troublesome minority within an apparently peaceful and, in many respects, privileged foreign minority group, the fifty thousand Jews of Rome. Rome generally tolerated foreign religions but insisted on "law and order". The Christians in Rome were clearly zealous proselytizers, and the majority of Jews in Rome had publicly objected to Christian troublemaking -- not just proselytizing, but brawls in the street. There were also horrifying rumors, compounded of Christian secrecy and what little had sifted out of Christian religious beliefs. In Roman imagination, a baby, Jesus, was eventually sacrificed and eaten. Worse, the process was often repeated in the Christian Mass. It was worse than the infant sacrifice for which the Romans cursed the memory of Carthage.

Just as importantly, major trouble was already brewing in Israel, which was a Roman protectorate. Zealots there (not Christians, but the Roman authorities didn't draw distinctions among these "Jewish extremists") were trying to take over the province and throwing out the Romans. Nero's persecution of the Christians including the martyrdom of Peter and Paul (64-68 AD) happened at the same time as this "Jewish Revolt" in Israel (64-70 AD) and its suppression (66-70 AD) by Vespasian and Titus.

According to the tradition, which was unquestioned by the early Christian communities, Peter was crucified at the base of the obelisk that stood in the center of Nero's circus on the Vatican hill, and Paul was beheaded outside of Rome on the Via Ostia. Both sites immediately became holy for the Christians of Rome, and small shrines were erected -- this was not a particular problem because the traditional site of Paul's death was on a road well outside the city and because Nero's circus fell into disrepute and disuse after his suicide. When Constantine embraced Christianity and made it the official religion of the empire, he built grand cathedrals at both sites, and these, after being rebuilt and further aggrandized, are the current cathedrals of St. Peter in the Vatican and St. Paul's Outside the Walls.

Since the time of Constantine, both Peter and Paul have been revered as the greatest of Christian saints and this reverence is heightened in Rome. The
commemoration of their martyrdom is celebrated on June 29, even though it is acknowledged that no one knows the dates of their separate deaths. But diverse interpretations of the preaching and philosophies of Peter and Paul have also contributed to the great disputes within Christianity. The major question in the split between Eastern ("Orthodox") and Western ("Roman") Christianity was the authority of the Popes as successors of Peter. Paul was said to have cast to the broader, more inclusive net and was known to have opposed the central authority of the Jewish high priests -- by extension he also would be against Christian central authority. The Protestant/Catholic split in Western Christianity was over the same issue of central Papal authority, with the added doctrinal dispute over "predestination" of an "elect" group who would get into heaven. Paul, in fact, had been the first to propose both of these doctrinal lines, in letters that both Protestants and Catholics agreed were authentic.

Meanwhile, Islam had also risen, and it, also, had its Peter-versus-Paul discussions. Paul was regarded as the villain who had reintroduced Hellenistic tendencies and thus reversed Christ's successful purification of Judaism. In fact the reason that Mohammed had to be created as God's latest prophet was to fix the damage that Paul had done. (This esoteric question is debated in Islamic university theology departments but seldom hits the streets, just as Christian Peter-versus-Paul debates today rarely take place anywhere except in theological graduate school seminars.)

Regardless of whether you believe or care about any of this yourself, these belief structures (or opposition to them) were so internalized in "Western Civilization" and in the Islamic world that they always influence the actions of people and governments, even though decision-makers may not even know where the belief structures came from. Leaders today justify their decisions by invoking inclusiveness (Paul) or advocating exclusivity (religious, ethnic, or racial "purity"), or by invoking centralism (Peter) or calling for decentralization.

Many of the sites on the Internet about Peter and Paul are tainted by religious bias -- it's only natural because Peter and Paul are still revered within various sects. Here are some of the less biased sources:

Halsall's "Ancient History Sourcebook" on Origins of Christianity (scroll down):
http://www.fordham.edu/halsall/ancient/asbook3.html#Origins of Christianity

Roman Historian Tacitus on Nero's persecution:
http://www.wsu.edu:8080/~wldciv/world_civ_reader/world_civ_reader_1/tacitus.html

A modern Christian site about Peter: http://cptryon.org/hoagland/travels/stpeterchains/ and
http://cptryon.org/hoagland/travels/stpeterchains/stpeterchains06.html

Roman Historian Dio Cassius on Nero, the fire, and blaming Christians: http://www.fordham.edu/halsall/ancient/diocassius-nero1.html

Ancient Roman historians about Christians:
http://www.csun.edu/~hcfll004/xtians.html

Catholic Encyclopedia on Peter:
http://newadvent.org/cathen/11744a.htm

And on Paul:
http://newadvent.org/cathen/11567b.htm

P.S.:  As terrible as the Roman persecutions of Christians were, they were only a small part of the standard arena bloodshed.  The total of Christians in the whole empire who were killed specifically because they were Christian has been estimated at four to ten thousand.  (Probably many more were killed in the general slaughters of prisoners-of-war, etc.)  Reliable histories talk about single days in the Colosseum on which there were more dead than the total number of martyred Christians.

By the time of Constantine, there were about seven million Christians in the empire.  If you were to count up all Christians who had ever lived in the empire until the time of Constantine, the total would be several times higher.  Almost all of these millions of individuals found a way to avoid martyrdom.

Although the Christians were usually not in public favor, contemporary historians state unequivocally that their plight aroused criticism and pity.  This was especially true during the vicious days of the first persecution, which was ordered by Nero, and it was certainly a contributing factor in his downfall.