The church of Rome, surprisingly, does not have any official story about how it was founded. My opinion is that it was founded by Paul, when he arrived and started preaching as described at the end of the book of Acts. This appears to be the implication (though not plainly stated) of the oldest document from the Roman church we have, the epistle of Clement to the Corinthians (often called "1st Clement" because there are other writings attributed to Clement of Rome, but none of the others are genuine), which even skeptical scholars accept, on linguistic grounds, as dating to the 90's AD. The official list of "Popes" is rather confused right at the beginning: Clement is either the second or the third or the fourth after Peter, depending on whether "Cletus" and/or "Anacletus" came after Linus and before Clement. We don't know if Cletus or Anacletus were the same person (possibly Anacletus "the upper Cletus" means Cletus Sr. and the other Cletus was Cletus Jr.) or if either or both was ever officially "bishop of Rome": there may not even have been such an official designation at the time; one possibility is that Greek-speakers and Latin-speakers in the city met separately with separate presiders (Kletos "called" is a Greek name; Clemens "merciful" a Latin one). Another possibility is that, since the later Xystos ("polished" in Greek) is often called Sixtus (Latin for "sixth"), somebody tampered with the list to insert Cletus so that Sixtus would be number six (including Peter) and somebody else thought he should be number six after Peter and duplicated Cletus into Anacletus and Cletus to make it so.
Howsoever it may be, Clement depicts himself more as the successor of Paul rather than of Peter, resolving a leadership crisis in Corinth with claims that he has the same authority as Paul to speak to them in God's name. He describes the sufferings of the church of Rome during the "Great Fire" persecution under Nero, telling how the women were gang-raped and the men crucified or burned alive. Paul is said to have been "sent on" to the furthest west (sent by the Holy Spirit? or by the Romans?) where he met "the fate of John the Baptist" (beheading)-- and Peter is mentioned as one of those who was crucified in Rome. I read it that Rome was one of the churches founded by Paul, but that Peter came there and ran it for a while after Paul went on to Spain, voluntarily or involuntarily.
But the New Testament contains an "epistle to the Romans" which purports to be Paul addressing a quite sizable congregation, that already existed in Rome, although Paul had not yet been there. Who founded it then? And why doesn't the book of Acts bother to mention a missionary who achieved the great coup of converting a large group right in the imperial capital? The body of "Romans" is most certain to be genuinely by Paul: it is arch-typical of Paul, in doctrine, style, and language; one scholar puts it "If this isn't by Paul then nothing is"; we might also put it that we can define the name "Paul" to mean "whoever wrote Romans" and judge all other epistles by whether they are "by the same author as Romans", since all of the features which distinguish the unquestioned epistles from the dubious ones appear most clearly in Romans. And yet, this one has more textual problems than all the other epistles together: Marcion's publication of it is described as lacking several verses in the first chapter, and whole chapters at the end, but we don't have a copy of it to know exactly what was and wasn't present; the copies we have from orthodox sources have serious discrepancies about the last chapters.
All other epistles claiming to be by Paul ("Hebrews" is anonymous, not claiming to be by anyone in particular) start in a fairly standardized manner, "I Paul, an apostle of the Lord Jesus, and [whoever is giving him secretarial assistance at the time], to the assembly [or 'brothers'] at [such-and-such place]..." They all finish with an invocation of blessings on the recipients, and an "Amen" (though many manuscripts omit the "Amen" on this epistle or that). In Romans, Paul introduces himself as an apostle but immediately launches into one of his run-on sentences; verses 1:7-15 belatedly mention that he is writing to the Romans whom he says he would like to visit sometime, but if we skip from verse 6 to verse 16 we see that this interpolation is actually interrupting the sentence. Presumably these are the verses that were missing in Marcion, who is accused of leaving it unclear who the book was addressed to. There follow eleven chapters about why Christianity is equally applicable to Jews and Gentiles, arguing from the Old Testament itself that the Torah was always intended as a provisional revelation, good and necessary for its time but preparing for a fuller revelation to come. All of this is difficult to reconcile with Marcion's views, and must have required some intricate tap-dancing on his part to explain how Paul is only relying on the "good" parts and not the "bad" parts of the Jewish scriptures; but Marcion is not accused of having failed to transmit faithfully all of this text. At the end of chapter 11, Paul wraps it up and says "Amen"; chapters 12 to 14 appear to be a separate letter, missing its opening, discussing a related yet distinct topic, about what sort of "laws" Christians should obey.
"The whole of the law is summed up in the saying, Love your neighbor as yourself" Paul tells us: a similar sentiment is ascribed to Jesus in the gospels, but Paul does not say (here, or anywhere where he echoes gospel sayings) that he is quoting Jesus. Laws imposed by the secular government should be scrupulously obeyed, for government in general is a good thing, restraining the wicked, and whoever holds power (even if the powerful are subject to human failings) is holding power because God allows it. He spends a lot of time discussing vegetarianism, deriding as "weak" those who think it is improper to eat meat. The reason for Christians to worry about meat-eating at the time was that most "butchers" were actually pagan priests (animals were always killed with some ritual dedication to some deity or other), so that in areas where a "kosher" butcher (dedicating the animal to the Jewish god) was not available, eating the meat might be considered an endorsement of idolatry. This was precisely the issue at the Council of Jerusalem, at which the opposite position from Paul's was decreed, that indeed Christians should refrain from eating any meat that had been dedicated to an idol. The text of Romans as we have it claims to have been written after this council, and would therefore represent an outright flat defiance of the Jerusalem church by Paul; I am more inclined to think this was written before the council, when the issue was still an open question.
The first few verses and the last one in chapter 15 are the "wrap-up" to this second letter, interrupted with a very long interpolation called the "Itinerary" section. Here Paul says he is about to visit Jerusalem to deliver contributions to the Jerusalem church from his churches in Greece and Asia Minor, and then intends to visit Rome on his way to Spain. The account of this visit in Acts gives a very different impression, that Paul hadn't had any plans at all to go to Rome, and indeed intended to go back to Asia Minor. In Jerusalem, Paul was denounced as a traitor to the Torah who should not be allowed to make any donations to sacred purposes (he was going to fund some Torah students who were taking the nazir vows of abstention from alcohol and hair-cutting, to show that he was no enemy of orthodox Judaism), and only escaped the ensuing riots with the aid of a relative who got him a military escort to Caesarea. Governor Festus (the authority in Caesarea) and king Agrippa (the authority in Jerusalem) interrogated him, and he stood on his rights as a citizen (Roman "citizenship" at that time was a rare status east of Italy). Agrippa, rather spitefully, said "If he had not appealed to Caesar, we would let him go; but, we'll send him on to Caesar" (this is Agrippa II, not the Agrippa who tried to break away from Rome some years earlier; but though he was more subservient to Rome than his father, he didn't like having his nose rubbed in the limitations of his power). And this is how Paul went to Italy. A few Christians had, indeed, drifted into Italy before: Acts 28:13 says Paul encountered some in Puteoli and stayed there a week, before being ordered to move on to Rome. Acts 28:14 kai-ekei-then "and from that place" the brothers who had heard about it came to accompany him, as far as the Three Taverns in the Appian Forum, for which Paul thanked them and took encouragement. The orthodox reading of this verse is rather strained: Greek has two demonstrative pronouns like English this "the nearer thing" and that "the further thing", which in texts mean respectively "the latter" (the more-recently mentioned) and "the former" (the less-recently mentioned), so the use of ekei "that; the further; the former" (related to ex "out; removed from") should mean that these brothers came from the earlier-mentioned place in the previous verse (that is, Puteoli); but we are told that here it means the brothers came from the later-mentioned place (that is, Rome). Instead of Puteolis travelling along with the road with him as far as Three Taverns, Romans come out of the city to intercept him at Three Taverns. There is a little shrine at the former site of the Three Taverns to mark this meeting.
The purpose of this strained reading of the verse is to cover for the strange fact that otherwise the book of Acts doesn't seem to have any Christians at all in Rome whom the epistle to the Romans could have been addressed to. Paul does not stay with any Christians in Rome, although that is always what he did when he had Christians to stay with; instead he rents a room "at his own expense" (no Christians even lend him a hand). He then talks to Jewish rabbis in Rome, who are curious to hear what Paul has to say for himself, because they have never met any Christians: "all we know is, that everywhere this sect is spoken against." The Roman government, unlike a lot of Jews, does not yet have anything against Christians (Paul was already on good terms with the brother of Seneca, the imperial tutor, and presumably did meet Seneca in Rome, whether or not we trust any of the letters they are supposed to have exchanged); Paul is allowed to preach freely all the time he is there-- so Acts concludes, without a hint that things were about to turn very sour.
Romans concludes with the “epistle of Tertius” and/or the “doxology”. Tertius (otherwise unknown) gives a shout-out to a long list of Christians he knows in Rome, with multiple “et cetera” indications that the list is far from exhaustive. This ends with the short wrap-up “The grace of Jesus Christ be upon you, Amen!” like Paul's typical sign-off, or with the longer wrap-up called the “doxology” (which invokes more elaborate blessings), or with both, in either order; or in some manuscripts we only get the doxology and nothing from Tertius; in others the doxology is inserted before the “Itinerary” as if the book were supposed to end there: we have no manuscript actually missing the Itinerary, but Marcion's text surely did not have it. We recognize one pair of names from the 1st century: Aquila (famous Jewish scholar, published a literalist Greek translation of the Tanakh which was regarded as better than the Septuagint) and his wife Priscilla, whom Paul befriended and converted after they were banished from Rome, along with all Jews, by Claudius. But when the ban on Jews in Rome was lifted, they did not go back, according to Acts, moving to Asia Minor instead; so they don't belong here, and were probably interpolated by some confused editor who thought they should have been on the list; perhaps Aquila had been suggested by some tradition as an answer to the puzzle about who founded the church of Rome? We recognize a name from the 2nd century: Hermas, elder brother of Pius who was bishop of Rome c. 150, and author of The Shepherd, a mystical vision of heaven found in many New Testaments (still canonical in Ethiopia), but rejected by the Muratorian Canon c. 170, despite praise for it, because it “was written in our own time.” Possibly there was a 1st century Hermas after whom the later Hermas was named, but I don't think so: we also find a “Herodion”, and I cannot see any member of the Herodian family accepting Christianity in the 1st century. I take it that the epistle of Tertius is a cover letter to the early-2nd-century church of Rome, enclosing some texts of Paul's letters that he has found; for whatever reason, he did not copy the “address” in the main letter (verse 1:1 ought to tell us who it was originally sent to), and the opening of the second letter is lost, hence all these editorial tamperings to explain why this book is found in Rome. A good guess for the “address” of the first letter would be the church of Berea, which did not survive, but is described in Acts as posing to Paul some probing questions about how his teachings fitted with the existing scriptures; Paul looks to be answering something very like what Bereans were asking. Whether the second fragmentary letter was to the same destination is difficult to guess.
It is frustrating that Acts breaks off without telling of Paul's trip to Spain or the “Great Fire” disaster, but presumably the “We Document” ends where it does because that is when Luke wrote it: in my view as a report to Peter and John, who came to Rome to check up on what Paul was up to and how his legal case was going. I think I can figure out when Paul was exiled to Spain: in the epistle to the Philippians, Paul seems to be in trouble (he says “Farewell!” repeatedly, as if thinking he is about to die) but says “They of Caesar's household salute you” indicating that he does have some powerful converts. Unfortunately, any tie to Otho, the head of Nero's “household”, was a back-fire (like his connection to Seneca, whom Nero turned on around this time, and would eventually order to commit suicide). Otho had been ordered to marry Nero's mistress Poppaea, as an excuse to keep her in the palace, but then genuinely fell in love with Poppaea; when Nero found out, he “promoted” Otho against his will to be governor of Farther Spain. A preserved ditty from the streets: “Is Otho banished? Yes and no / That is, we do not call it so / It was for adultery, more or less / It was his own wife he caressed!” Perhaps Nero decided to ship that troublemaker Paul off to the end of the world at the same time (Otho went on to support the revolt against Nero by Galba, governor of the larger and more prestigious Nearer Spain, and expected the childless Galba to name him as successor; when Galba picked Piso instead, Otho killed Galba and Piso to take over briefly as Emperor, unfortunately discovering that the army expected to be paid off with more money than he could raise). If I have the sequence right, then indeed Peter ran the church in Rome for a few years in Paul's absence. I do accept that John came with Peter but left (although Acts of John , the only source on that, is late and dubious), because Nero's initial reason for accusing the Christians of starting the Great Fire (confirmation was obtained through torture, of course) was that Christians allegedly had predicted it in advance: I think Revelation 18:18 is what he was talking about (most scholars don't think this is from John, but I do).
Linus (a companion of Paul, not Peter) headed the survivors of Nero's persecution probably because he was the most senior person left, not because any succession had been planned in advance. Other important Christians managed to get out: Silas was also of Paul's party, not Peter's, but showed up in Asia Minor with a "letter of introduction" from Peter not Paul (I accept "1st Peter", unlike the thoroughly pseudepigraphic "2nd Peter", as likely to reflect Peter's thought), tending to confirm that Paul had not been in charge at Rome towards the end. I will discuss Mark when we come to Alexandria. Trophimus, a companion of Paul, made it to Arles, where his successors claimed that he had been converted before Linus, and therefore that they, rather than the bishops of Rome, were the true successors of Paul. Sometimes they called themselves "patriarchs" of Arles; although no other patriarchs recognized them as such, they remained a thorn in the side of Rome for centuries.
Perhaps this was one reason Rome shifted its focus from Paul to Peter, or perhaps it was to combat the claims of Antioch. A simpler explanation is that they had (or at least, sincerely thought they had) the body of Peter (the place, south of Rome, where Peter's body was originally dumped is still marked by a little shrine; the body was retrieved and re-buried in the Vatican catacombs, then a cemetery) whereas nobody has, or claims to have, the body of Paul (bodily relics were very important to the ancient and medieval mind-sets). Oddly, the first claims that the bishops of Rome were successors to Peter is found in Ebionite literature: the "pseudo-Clementine" literature claims that Clement was converted in Judea (I seriously doubt that he was Jewish) by Peter shortly after the crucifixion (he would have to have been very young!) and early tapped as Peter's successor (directly; Linus is left out of the story); and of course Clement and Peter like James the Righteous wanted nothing to do with that infiltrator Saul of Tarsus (never called "Paul") in these books. Italy was a major source of pilgrims to Jerusalem from early on, Antioch was a common enemy, and the church of Rome already had a wide reach: but in seeking an alliance with Rome, the Ebionites were barking up the wrong tree. The epistles of Paul always remained doctrinally foundational in Rome; the "Nazarene" schism in the 3rd century may have been a recognition by some Ebionites that they needed to agree to accept Paul's conversion as genuine if they were ever going to be in communion with other churches. Pope Damasus (late 4th century: finalized the Roman canon and commissioned Jerome's Latin translation) gave Ebionite hopes a death-blow by announcing the doctrine of Mary's "perpetual virginity": politically, this meant that James the Righteous was not considered a brother, but only a cousin, of Jesus; and his successors not ranked as important.
The Vatican archives do not become anything like complete until Innocent III (13th century) due to frequent sacks of Rome, and the problems of preservation (one researcher noted an 8th-century land grant which had been recopied centuries later, the original attached in an envelope; but a look in the envelope revealed that the original "has the consistency of a pile of sand"), but archivists have recopied old records wherever they could be found, and we have some tantalizing bits of old stuff. Fragmentary administrative records from the 2nd-century Pope Victor reveal that the church of Rome was already supervisory over numerous churches, over all Italy at least; a principal function was accounting for donations and redistributing them in the nature of a mutual-insurance association, that is, as with many "fraternal societies" from that day to this, a major social role of the church was to reassure members that their burial expenses and surviving widows and orphans would be taken care of if anything happened to them. The top posts were assigned strictly by seniority (not chronological age, but time since ordination as a priest); one worked up to “bishop of Rome” by outliving everyone ahead. Outside Italy, Spain and also Greece (however little the Greek Orthodox now like to remember this) were unquestionably loyal in the early days, even though Gaul was iffy (bishop Irenaeus of Lyons urged c. 170 that all Christians in Gaul obey Rome; but he would not have had to say so if it wasn't an issue): we have a document from Damasus confirming (it was not an innovation) that the bishop of Thessalonica (Paul's first foundation in Greece) was Rome's "vicar" in Greece, and the bishop of Cordova (capital of Further Spain, probably where Paul went from Rome) early played a similar role in Spain.
North Africa was also a problem. There were recurring schisms in the western church from the “rigorists” who wanted to take a harsh line against Christians who co-operated with the authorities, even slightly, to save their lives. The first antipope in Rome, Hippolytus, objected to Pope Calixtus as too lax about re-admitting the “lapsed”: the persecutions had ended under the Severan dynasty (one of whom included Jesus among his portrait gallery of wise men, alongside other greats like Pythagoras and Socrates and some charlatans like Appolonius of Tyana and Simon the Magus), but when followers of the two rivals began fighting in the streets, Hippolytus and Calixtus were both banished to the mines of Sardinia; a little experience of hard labor softened the attitudes of Hippolytus, who apologized and made up with Calixtus, writing some valued theological writings which earned him sainthood. But later there was another rigorist antipope Novatian, and in Carthage bishop Cyprian (also later sainted) tried to steer a middle line, and got flak from both sides, so that for a while there were three bishops of Carthage, one aligned to Novatian and another attacking Cyprian from the opposite side of the spectrum. We have correspondence between Cyprian and Pope Stephen I, who agreed on re-admitting the lapsed but only after sincere acts of penance, but disagreed on “re-baptism”. There were two cases where re-baptism might be considered: if someone had converted to “Christianity” through one of the unorthodox Gnostic sects, but then joined the orthodox church, Cyprian saw no reason to re-baptize if he had been baptized “in the name of Jesus” or “in the name of the Father, Son, and Holy Spirit” (both formulas were in use) while Stephen insisted only a baptism by an ordained priest was valid; but if someone had left Christianity for some other religion (Manichean, Mithraist, the cult of Serapis, etc.) and come back, Cyprian thought re-baptism necessary while Stephen took the “once saved, always saved” position (as modern Baptists put it). Eventually, in the “Donatist” schism, much of North Africa went over to a hard-line rigorist position, refusing to recognize any priests or bishops who had compromised with persecutors in any way, while Rome maintained that a properly ordained priest always remained a priest. Major debates were held between the pro-Rome bishop Augustine of Hippo and the anti-Rome theologian Pelagius (literacy was low, but public readings of intellectual tracts with spirited Q-and-A afterwards, think “Chautauqua” meetings, were a popular entertainment; the masses were surprisingly sophisticated about such controversies), bringing out the core issues.
Pelagius believed in free will, and thought the sacraments derived their efficacy from the decision of the participant to accept the grace of God; the role of the priest was solely symbolic, to assist in turning one's mind to God, and a priest who had committed grave sins was not appropriate in such a role. Augustine denied that any of us have the power to choose good: grace flows from God without any possible help from us; and if a priest fails to be virtuous, that is unsurprising, since all men are prone to sin. To use an anachronistic metaphor, grace flowed through the sacraments like electricity if a “circuit” is closed: baptism confers grace if performed by a validly ordained priest, regardless of his own state of grace or sin; the ordination in turn was valid if performed by a validly ordained priest, and so on back to the 12 chosen by Jesus. Pelagius, by leaving it up to us to judge whether a priest is good enough to work the sacraments, was undermining the whole “apostolic succession” structure, creating insoluble uncertainty. Rome decreed that Pelagius was teaching heresy, and Augustine triumphantly said Roma locuta, causa finita! “Rome has spoken, the case is over!” without really grasping that this is just what Pelagius denied. Pelagius did have to flee Africa, but the “patriarchs” of Arles supported him. In the 5th century, Pope John I (his given name was “Mercury” but he decided to change it, the first to take a “throne name”) summoned the bishop of Arles to answer for his Pelagian heresy, and condemned the “contumacious” fellow in his absence when nobody from Arles showed; a bishop Germanus of Auxerre was despatched to Britain to combat Pelagianism there, but found that the Saxon invasions were making it too difficult for him to even get ahold of most of the churchmen there. The "Celtic Church" of Britain and Ireland would remain largely independent until Henry II invaded England, with the excuse of forcing Ireland to submit to the Pope-- which is ironic, in view of Catholicism's later identification with anti-English resistance in Ireland.