Rise
There is no need to suppose that miraculous mass conversions to Christianity took place during its early years. Rather, up until around 350AD Christianity had a steady growth rate of 40% per decade. This steady exponential grow was sufficient to convert a majority of the Roman Empire. As with new modern religions such as Mormonism, conversions would have been via social networks. Conversion invariably happens when a person is surrounded by believers, and detailed understanding of a belief system generally only comes after conversion. Christianity began by Jesus converting his family and friends, and spread from there.Christianity's initial spread outside of Israel was helped by the existence of a large population of diasporan jews, especially in Greece. The jews at that time were actually managing to convert some gentiles to their monotheist religion. However, then as now, their eating habits and style of dress set them apart from society. Thus there existed a population of jews who wanted to integrate more easily into society, and also a population of gentiles, the "God fearers", who were partially converted to judaism but had not yet fully joined the jewish community. These two groups were the people that missionaries such as St. Paul initially converted, bootstrapping from existing social connections Israel had to the diaspora.
Rational choice
If you've been following my previous blog posts, you'll know I argue that adopting religious beliefs can be a rational choice (even if those beliefs sometimes lead you to do silly things). Early Christianity provides some beautiful examples of this.Early Christians formed a much stronger community than existing paganism. They really were into the whole love-your-neighbour thing. This meant that when plagues struck, Christians tended to care for their sick fellow believers, rather than sensibly barricading themselves inside their houses or heading for the hills. Simple ministering such as providing food and especially water to the sick can reduce death rates considerably. By looking at gravestones, a statistical case can be made that Christians really did live longer on average than pagans.
For women especially, Christianity provided advantages. Early Christian
communities were actually skewed toward female membership, in Roman cities
where the population was heavily skewed toward male.
Pagan custom at the time allowed infanticide, and male children were valued more than female children, so female newborns were often killed. The resulting population skew also made females a scarce commodity, and they were therefore often forcibly married, and at an early age [1]. The earliest legal age for marriage was 12 (generally to an older male), however marriages at earlier ages were not punished. Husbands were able to force women to have abortions, and abortion at that time involved either a not-quite-lethal dose of poison, or a doctor reaching into the uterus and pulling out the fetus (perhaps with the aid of a suitably shaped hook). Also, while female infidelity was frowned on, males had free reign. Contraception at that time was largely ineffective.
Christians from the start forbade abortion and infanticide as murder, and required fidelity from men as well as women. These things, which now cause a great deal of grief, were at the time huge wins. Christian women also tended to marry later (only 7% marrying before age 13 as compared to 20% for pagans, and 48% marrying after age 18, as compared to 37% for pagans).
If Christianity today seems backward, it is because we now take for granted the advances it introduced.
Fall
The Roman Empire, much like the USA today, was a more or less free market for religions. Christianity was persecuted somewhat, but this was largely because of their anti-competitive practice of demanding worshippers worship their God alone. Other cults with similar requirements were persecuted in a similar manner.However, starting with Constantine, Christianity became a state sponsored religion. It remains hard to set up competing religions in Europe to this day -- while it is not illegal, bureaucracies are set up to make it very difficult. State sponsored religions need not so actively drum up religious fervor to survive. They skew towards supporting the state and the powerful and wealthy to the detriment of commoners. They also represent a single flavour of religion, where a religious marketplace supplies a wider selection--something for everyone.
This has in the long run lead to large numbers of people in Europe having no religion. Note that this is a status distinct from a reasoned assertion of atheism or agnosticism. It is rather a case of no religion being available that is well suited to their needs. Such people remain easy prey to new cults and various lesser forms of superstition.
[1] An argument that doesn't entirely make sense. The scarcity of females might just as easily have granted them greater power. Suffice to say then that Roman pagan society was nightmarishly sexist, as have been many cultures.