Part 19: Delta Green explains about more about Christianity and it's proselytizing.
I always understood that Christianity succeeded because there is a duty to proselytize built into the religion.
Part of it.
The scene was basically set for the rise of Christianity around the 2nd and 3rd Century. Before, it was mostly a religion of the poor and it spread at such, converting mostly slaves and lower social classes with the promises of Paradise after death and other such things. The great weakening of the traditional cults, the rise of new pagan cults like Mithra (who was far more elitist and militarist) and the constant troubles of the 3rd Century led to people looking for new faiths to believe in. Christianity was there, spread throughout the Empire's cities, organized and promising salvation and redemption to all.
Also, the communal feeling of Christianity was far closer and familial than the Pagan cults. After all, on one hand you had distant, fairly uncaring gods with giant egos and tempers to match; on the other, you had God, loving and forgiving, taking a personal interest in Humanity's plights through his Saints and his Son. Bad things might happen to you, but you could be assured that God wasn't doing it simply to laugh at you and that your reward was waiting.
Furthermore, if records are to be believed, there were miracles like mad around that time. I mean, seriously, we have hundreds upon hundreds of reports of various miracles happening to both Christians and Pagans. Unlike the Pagan cults, the Christians had a fairly good case to present for God's presence and interest in helping Humanity.
Lastly, the major impetus of Constantine's legalization of the religion and eventual conversion. Mind, it was partly politically motivated, but by the end Constantine was a true believer.
The thing that decided it politically for Constantine was that Christianity preached pacifism and social order. If there were trouble, he could expect the bishops to be on his side in calming down the public, unlike the far less controllable pagan cults. Before, the Church was secretive and persecutions, especially that of Diocletian in 303, drove the cult into clandestinity. After 313, Christians began to repay Pagan cults for the earlier persecutions and retaking lost properties, and Constantine did support them legally in such endeavours.
Mind you, he did come to regret it slightly with the constant battles between sects of Christianity, especially the Donatist heresy. Hence why he called for the Nicean Council, which he presided as moderator in his role of Pontifex Maximus.
Even then, the Nicean Creed wasn't fully accepted as the primary form of Christianity until well after Constantine's death. The Arians held much sway in the Empire until 330 and continued to hold influence in the Imperial Court afterwards.