More importantly, Paul made the cult palatable to the Hellenistic world which at that time represented the middle and monied classes of the middle east. The Romans tended to despise christianity, when they actually reached the point where they could distinguish the cult from Jews in general. Jews were notorious to the Romans, and christians were indistinguishable in this regard, because they refused to pay lip service to the civic religion. You could profess any religion you chose, so long as you went down to the temple once a year and gave the priests a chicken to slaughter (the Romans practiced divination based on the behavior or entrails of birds). As long as you did that, everything was hunky dory. Jews (and the early christians, who were not even known as christians, were indistinguishable) loudly and publicly refused to do this. The tales of early persecutions of the cult are largely bullshit, but when it did happen, it was their enraged neighbors who didn't want a bunch of Palestinian hill billies bringing down the wrath of Rome on them.
It was only late in the second century that the cult becaume wide-spread and visible in the empire. When there was official persecution, it was because the idiots meddled in politics, and showed a rare genius for backing the wrong horse. Septimius Severus, who rose to power at the end of the second century, slaughtered a great many christians--but not because they were christian, rather because they had backed the opposition when he was fighting for the imperial crown. Modern christians, of course, make noble martyrs of these clueless meddlers.
The most popular cult among the Legionaries, the the people in the empire apart from the Patrician class whose opinions really mattered, despised the christians as followers of a cult for slaves and women. The cult of Mithras was wide-spread and solidly entrenched in the legions. It was not until the early 5th century that the cult made any headway in the legions, and that was only after they had been devastated by the upheavals contingent upon the Gothic and Vandal rebellions. In the attempt to recover, the empire filled its legions with Goths and Vandals, most of whom had become Arian christians, which is to say, heretics.