The success of Christianity was by no means inevitable. A combination of factors led to its advent. Chief among these were the spiritual and religious climate of the time, the zeal of the early Christian proselytes and the eventual sponsorship by the court of the Roman Emperor.
Syncretism was the rule of the early Roman empires day. The message of the Christians was easily absorbed by some of the more educated Hellenistics throughout the Jewish world. As time went on, these would be even further divorced from what we might call pure Judaism (that is the traditional variety derived only from Jewish scripture). Christianity had something more spiritual to offer than the imperial cults and the mystery religions and may have seemed more inviting than Orthodox Judaism to many of the Diaspora Jews living so far from their homeland. The Roman cults were highly secularized and had no theology, and in fact barely even had a mythology about them. And the mystery religions imported from eastern countries were very secretive and exclusive, thus stymieing opportunities for mass conversion. In any event too foreign for even a Diaspora Jew.
During the First and Second centuries, while the Apostles were running about spreading the Good News, the entire Mediterranean basin was under the authority of Rome. As oft happens when a general peace is achieved, trade picks up, including the trade of intellectual goods. What this meant for the people around the Mediterranean was that for the first time in recorded history many widely varied formulations of religious thought were being circulated and blended together. For instance, the communal meal so essential to early Christian life was hardly unique to the Christians. Followers of Isis and Mithras among others are known to have engaged in such feasts, replete with sacrificial offerings and remembrances of world-saving feats (Mithras slaying the bull). And, contrary to what is often thought, many contemporary outsiders looking at early Christianity would have assumed similar religious belief structures existed for all these groups. In a situation where one cult is as good as the next, it is not hard for one to come to dominate the others. For they are all based on the same principles and rituals (to an outsider at least).
In the years following the death of Jesus, appropriately called the Apostolic Age, the original disciples of Jesus were at first disenchanted by their mentors sudden death and the apparent lack of change or revolution. Later their motivation was renewed by his teachings. That is, his message as they had known it originally was understood apocalyptically. With his death and the passage of not one, but two, unsuccessful Jewish rebellions, the Apostles began to adopt, ever so slowly, a more universal understanding of the Jesus Movement. His message was reevaluated for its appeal to a greater majority of people. With this universal approach to the message, they were able to travel the Mediterranean and found new communities among less and less categorically Jewish peoples.
Finally, in reference to the society in which Christianity incubated, it is necessary to remember that the one thing that was the essence of the difference, so far as the pagans were concerned, was the Christian communities reluctance to participate in what we call state sacrifices. In the ancient world, religion was still linked to the machinery of the government. Prayer and worship, while not always as mundane as taxes or civil service, were still a part of the greater social entity which was the state. So, to decline to sacrifice for the welfare of the community as a whole, the Christians put themselves in a position where society at large would hold them suspect and perhaps even, at worst, subversive.
Originally, these Christian communities were subsets within the extant Jewish diaspora groups scattered throughout the Roman Empire. Were it not for the Apostles feverish activity, the seeds of the Christian religion would never have left the Holy Land. Through his letters in the books of the New Testament, we see Paul telling his converts in places as far away as Corinth and Philippi, Thessalonika and Rome that which he has already explained to them on previous trips. For years he maintained these correspondence based relationships. Making sure that his new converts did not stray to far from the path he established, while reaffirming their beliefs with written words representing the oral tradition that Christian Jews form the Homeland (Judea) were still telling to each other at their communal dinners. Through these mens copious writing, the nucleus of Christian doctrine and ritual was put down on paper for the first time.
Several centuries later, however, would come a self-styled thirteenth Apostle. If the definition is kept to its Greek root, then this man truly was one of them, if not the greatest. His name was Constantine. Were it not for his espousal of the sapling faith -for it was hardly a seedling anymore- it may well have been just another of countless spiritual groups throughout the empire.
Constantines conversion is not really all that astonishing from the point of view he or his contemporaries might have had. Adoption to any particular religion was not something that was all engrossing. As a matter of fact, it is well documented that throughout his remaining years Constantine the Great did not ever fully convert to Christianity until he was on his deathbed (he was baptized in May 337). He is just an ultimate example of the syncretism of the times. However in this case, and it was special, he was the emperor of a newly unified empire and thus no mean convert. As such, his new world order was designed to cement him firmly as the only true ruler of the singular political entity in the known world. For Constantine, he must have truly felt he was as close to God on Earth as any one man could come. How convenient was it then, that a similar creature had once roamed a backwater province claiming a similar thing for himself. Demigods and divine humans were a fact of life in the ancient world. Likewise god-kings were readily accepted and easily understood, especially in the Hellenistic era. Constantine, in supporting Christianity, was perpetuating his own cult of personality through a vessel which already had an established group of followers with a King/God model. These formerly persecuted people were more than willing to accept the eccentricities of a patron Emperor in exchange for legitimization.
With the backing of the penultimate (if you include God) authority in the universe, the bishops and Church leaders were now able to refine their faith and organize their rituals. Without having to dodge executioners, Christianity was able to spread even more easily than it had before. During the Pax Romana, it spread and was largely tolerated by the Roman government. It was only in a social context, not political, where it had its largest problems, as I wrote earlier. In this new era of Constantine, the Dominate period, Roman rule was much more harsh and repressive. In fact, you were either cultivated or destroyed by this new government. So, for the Christians to be on the Emperors good side put them at a distinct advantage over every other cult or religion. In a matter of a few short years, Christianity had become the official faith and eventually would become the only one legally allowed. A reversal which was only possible in such a bureaucratic nightmare through the power of an Emperor.