The quick answer is that it wasn't easy. It took three centuries for Christianity to become officially tolerated and protected by Constantine, and nearly another century and a pagan emperor before it became the state religion under Theodosius. Although the empire was seemingly largely Christian by the fifth century, in reality it most definitely was not, as in the undocumented countryside paganism must have survived. From the Syriac historian John of Ephesus we also know that there was a concerted attempt by Justinian to convert tens of thousands of pagans in Asia Minor in the sixth century - the same must be true on a greater scale in even less accessible regions. All sorts of polytheistic beliefs also flourished outside of the Christian empire, which took even longer to overcome and there were plenty of setbacks, so the Christianisation of Europe actually had a very long and troubled history.

I'll mainly cover how Christianity became popular within the Roman Empire, but I'll skip over the first three centuries of Christianity as I know very little about it. It is worth noting however that many gentiles did convert to Christianity throughout this period, so much so that by the time of the Tetrarchy Christianity was the faith of 10% of the population (according to Rodney Stark), or less than 3%, to quote the figure suggested by Peter Heather in a recent research seminar. Still, it is clear that pagans converted in large numbers even without state intervention, even when Christianity was under threat from certain emperors. From a purely rational perspective, this seems illogical, but humans are not rational at the best of times, so we shouldn't see history in this way either. Perhaps the earliest converts did so out of social dissatisfaction with their ancestral religion, perhaps it was due to genuine belief, or it happened for more cynical reasons, I don't think we can ever know - the psychology of conversion is complicated, but at least it should be obvious that people's beliefs can change for all sorts of reasons, even if paganism had ancient roots. The same after all can be said for Christianity, which had its roots in Judaism, another faith with a very long history.

We also shouldn't see Greco-Roman religions as similar to the more institutionalised Christian church we are all more familiar with, simply because they were decentralised and lacked a central leadership figure. Instead, a huge variety of cults competed against each other all at the same time and innovation was the norm. The same was true for Christianity, as followers of competing doctrines fought against each other through the history of the church, so there was never something as simple as a conflict between Christianity and paganism.

So what happened in the fourth century that made Christianity more attractive for converts? I would suggest that there were two main factors: one, that there was a trend for more and more Romans, particularly emperors, to embrace some form of monotheism already, and two, that Christianity was not constantly persecuted, so many individuals knew of Christians and their faith already in a relatively safe environment. For the first point, I thoroughly recommend Paul Stephenson's Constantine: Unconquered Emperor, Christian Victor (2011), as he wrote in a very accessible way about the increasing influence of solar monotheism under the Severan emperors and Aurelian, so from that logic, Constantine's change from solar monotheism to Christian monotheism wasn't that strange - he already believed that he was protected and favoured by one particular god, so it wasn't an inconceivable leap of logic for him to embrace Christianity, especially as he already had Christian advisors at his court. By extension, this must have applied to other adherents of similar pagan cults as well.

As for my second point, it is always worth stressing that before the Great Persecution of Diocletian Christians can be found in positions of influence. Lactantius, the Christian writer who later lionised Constantine and damned his political enemies as persecutors, was for instance first invited to teach rhetoric at the imperial court by Diocletian, whilst Constantine's mother, Helena, was most likely a Christian already and thus influenced her husband, the Caesar Constantius, to be moderate towards Christian communities in the west despite Diocletian's policy of persecution in the east. At the same seminar I noted above, Peter Heather also made the very good point that we have no positive evidence that Constantine wasn't a Christian from the start, since he may well have hidden his personal faith due to the political situation. When his victories had overturned existing norms, he can then safely out himself as a Christian (having first portrayed himself as a solar monotheist). In any case, once there was a Christian emperor, it became a wise career move for cynical-minded people to convert in order to ingratiate themselves with the new regime, and likewise for the truly devout to be more obvious about their faith in public.

It is also often said that Christianity adapted many elements from traditional pagan beliefs and that this made it more popular. To a certain degree, that is correct, since no matter how powerful the Church was it could not regulate the faith of those in the countryside, and as I said, paganism must have been a strong force outside of urban centres throughout the Late Roman Empire, even if very few Christian writers wrote about them (they were generally educated and based in the cities, so they had no interest or need to write about rural bumpkins). However, it would to be too far to say that Christianity was only popular because it appropriated pagan traditions. This is I think very misleading, simply because Romans at the time would not have seen it this way. The vast majority of our sources were written by educated men, all of whom enjoyed a classical education and embraced the idea of paideia (the intellectual taste and mentality of an educated aristocracy). If they were Christian, they would have no problem with depicting pagan myths in churches or engage in traditional rituals such as Lupercalia, which annoyed a fifth-century pope but was clearly enjoyed by many. It was tradition and tried-and-tested by their ancestors, so why on earth would people abandon them or see them as contrary to their new faith? Christianity was never particularly good at getting people to live an exclusively apostolic life in any case, despite the many angry diatribes written by men such as Jerome and Pelagius - as always, people are people and they did not want to abandon their past or their habits, a very human instinct that is I think very easy to understand. As such, in the majority of the cases we shouldn't see the appropriation of certain rituals as a deliberate cynical attempt by evil Christians to make their religion more popular, but as the osmosis of cultural norms that transcended the blurry boundary between different beliefs. I'm sure there are many counter-examples, but this is I think a useful way of looking at the big picture.

Lastly, it is also worth pointing out that paganism was not persecuted out of existence. Emperors from Constantine onwards did issue laws that increasingly limited state support for cults and sometimes even laws that did make life hard for certain groups, so it is easy to get the impression that paganism was constantly under threat. This is however the impression Christian emperors and writers wanted to give to the reader - they desired a Christian empire, so they legislated against certain practices and denigrated the popularity of paganism. In reality, pagan elites continued to thrive throughout the fourth century, so much so that we can't even really say that there was a 'pagan' party fighting a losing battle against a Christian tide, as pagan and Christian officials worked together to deal with the empire's problems. Even when they treated each other as enemies, we have to look for personal and political reasons for conflicts as well, rather than just to focus on their religion. As for the destruction of temples that we know about, such as the famous Serapeum (which did not contain a library by the way...), they were seemingly the result of riots initiated by Christian mobs, rather than by imperial edicts.

I guess what I'm trying to say here is that we should be aware that 'pagan' and 'Christian' were not definitive categories for people in late antiquity. Many people were devoted to their beliefs, but many others found it easy to cross these boundaries, whether out of genuine faith, their cultural context or for more cynical reasons. People also identified themselves by their ethnicity, their social position and their relation to others, so to get a sense of how they converted (or not), we have to look at the bigger picture, which actually makes everything a lot more complicated.

This answer got a bit too vague towards the end, so feel free to ask me more specific questions about religion in the Roman Empire :)

I've written about this topic in the Irish context a lot before, so unlike shlin28's excellent post about early Christianity in the Roman Empire, I'll talk about the religion's spread in temperate Europe. I think your question is phrased in a problematic way: most Europeans before the Reformation didn't really give up all of their ancient beliefs; they merely articulated them in a more Christian way. In Ireland, for example, warriors invoked Jesus or their regional saints for victory in battle instead of their old gods in a form of military magic and people would voyage to healing springs associated with a local saint which was more often than not the Christianized form of the territory's former local deity. Another common practice in England and Ireland was the theft of the Host from Mass for its magical abilities.

Now, none of those beliefs I've written above are very Christian. They arose out of necessity as early missionaries realized that old beliefs could not be totally eradicated because they were part of the daily life and fundamental worldview of pre-Christian agrarians. To avoid complete alienation, the missionaries figured it was easier to just coarsely Christianize magical belief instead of rooting it out (which later reformers would try from the middle ages to the Reformation). When Christianity justified those forms of magic by attributing them to Jesus or God, there was no real barrier for an Irish pagan to become an Irish Christian - there was less of a cataclysmic break from the past than a blended transition where elements of old structures of belief survived because the clergy couldn't risk alienating the majority of the population.

You have to understand that pagan peoples, expect maybe the druids, had no real philosophical attachment to their faith, but they were attached to the magical figures and places that could help them in their everyday life. When those figures became Christianized, it wasn't such a big deal for the majority of people. Their local gods became Christian saints (for example the Irish goddess Brigit was transformed into the Saint Brigid) and their healing springs and magic wells became Christian holy sites.

The role of magic in the Irish (and generally temperate European) perception of religion is also important to consider. Christianity was a new and more powerful form of magical manipulation, with a clear dogma and text which contained demonstrable examples of the new god's power. Christianity was consequentially used by new practitioners as healing magic, a form of divination and battle magic.

Christianity with its clear doctrine and corpus of literature, filled with apparently magical events, could justly assert itself as a fundamentally more powerful way of attaining magical power. Drawing on Old Testament God's ability to destroy cities and flood the earth, Christianity was evidently more powerful than paganism whose gods were more localized and had more diffused power. Why would you worship a bunch of gods with different, limited powers when you could worship one supreme god who could give you all your benefits at once? With Christianity, one could harness a single god's power for prowess in battle, fertility for their crops, protection from weather or plague etc. instead of having to supplicate a whole bunch of different deities and spirits. Not only did Christianity simplify the process of gaining magical powers, but it also had a whole corpus of events in the Bible that could be used as proof of the new Gods' power, while Ireland's pre-Christian belief system had no doctrine or dogma and thus lacked Christianity's persuasive power.

In many instances, these supernatural beliefs were not even Christianized; Irish kings still abided by their geasa; magical taboos whose breaking could lead to death, while villagers in Ireland and across Europe would practice explicitly non-Christian magic. Some of the old gods still survived on a folkloric level as well; the Christian church attacked belief in Fortuna (belief in fortune may seem secular today, however Fortuna was the Roman goddess of luck). In parts of Scandinavia and Germany, the old Germanic gods Freya and Odin held a place in popular belief long into the medieval and early modern eras.

So to answer your question: most Europeans did not give up their ancient beliefs. In many instances, their magical beliefs, rituals and figures were coarsely Christianized and only expunged centuries later. Christianity was appealing because it was perceived as a powerful and new form of magic that could be used to manipulate the physical world, and was in many instances syncretized with older magical practices.

Another follow-up question, if its not too much trouble:

St. Patrick is often credited with almost single handedly converting the island of Ireland from Paganism to Christianity, can anyone give a detailed account on what exactly happened?

Rodney Stark (referenced in /u/shlin28's comment) wrote a book on this from a sociological perspective. The Rise of Christianity (Princeton 1996) uses modern sociological modeling and primary historical sources to address this exact question. Well written for a general audience.

Followup question: I imagine some answers will highlight the way Christianity was able to appropriate and adapt pagan rituals into its own practices.

Can someone explain how this was done? The way I usually see this argument pop up makes it feel as if "Christianity" as a unified entity with centralized leadership existed to sanction which rituals were and were not to be included into the religion.

Was this the case, or was it a more bottom-up gradual process?

Are there many of such pagan rituals and practices that survive are still practiced in Christianity today?

Thank you!

I would suggest that your metaphorical language is misleading you. What do "thousands of years of inertia" and "ancient beliefs" mean? No individual pagan had believed anything whatsoever for a thousand years, or even a hundred. No individual's belief is any more ancient than the believer himself. At most, he might be a little more attached to his belief because he learned it from his parents or grandparents; but then, adolescent rebellion is also a thing, so that could cut both ways.

In thinking about history, we sometimes see movements, trends, Zeitgeists, and fads; but it is a mistake to speak of these as though they were things in themselves, with their own causative power. "Inertia" used outside of physics is a metaphor, and metaphors should be replaced with the real thing the moment they become confusing, or ideally a few minutes before. In this case you should ask something like "How did Christianity overcome the tendency of people to believe what their parents believe", and then the answer is clear: There is no puzzle. Sometimes people encounter a new thing and decide that their parents were wrong, that's all. There's no "thousands of years of inertia".

In the end it's all about a finite number of individuals making their own decisions. What their ancestors a thousand years earlier believed can, in principle, be an influence on those decisions - but I would not expect it to be an important one.

May I be permitted a clarifying question? The OP appears not to be limiting the spread of Christianity to Europe or the Near East. My original thought was whether the OP was really interested in other, more primitive cultures, perhaps such as those in New Guinea, Polynesia, Africa, or in the Americas.

I imagine the "answers" to this context would be much different.

So, for OP, are you referring to specific "pagans"?

And for others, would you have a way of answering my thoughts on the other cultures not yet mentioned? I have my own speculations on these, but nothing concrete or sufficient as a top-comment on this sub.

Thanks all!

I originally sought to answer this question, but I fear that my answer is not concrete enough to warrant a proper comment, so I'll phrase it as a question instead.

Marc Morris, in The Norman Conquest: The Battle of Hastings and the Fall of Anglo-Saxon England, talks not only a lot about the invasion itself, but the events prior to and after it. Obviously, these events are tied closely to the kingdoms of Norway and Denmark and the politics of both. His depiction of religion for expanding Scandinavians, particularly the monarchs, seems to be that religion in Scandinavian nations was not as deeply personal as it might be today or in other cultures of the time. He implies that kings converted for largely political reasons, and Scandinavians settling in Latin/Frankish lands, such as the Normans, quickly and fluidly "Latinized" without much regard for the beliefs and culture of their ancestors.

Is this an accurate depiction of the... I don't know... theo-political atmosphere of Scandinavian nations and their satellites? I'm not even wholly comfortable using the word satellite here, but for lack of a better word...

(edit: having finally read all the comments above, it seems that both approaches that I discuss below have been addressed quite well, at least in relation to the very early years of Christianity's spread. The following is less a contribution of my own knowledge than the suggestion of a very useful book which extends these questions into (ostensibly) solidly Christian civilizations in the early modern period)

(edit 2: I have rarely read and never posted in askhistorians before, so I am unfamiliar with conventions of address. Apologies for the rather patronizing first paragraph...)

There are various ways for Christianity to "overcome" paganism--some are military, some are political, some are intellectual, etc. It is important to note that there is a difference between Christianity being adopted as the religion of the Roman state and it conquering paganism completely. Part of the question here is who we are talking about: kings and "intellectuals" (in their various historical guises) or commoners?

The former looks like it has been addressed thoroughly in this thread.

If you want to think about the latter well into the modern past, consider reading Carlo Ginzburg's "The Cheese and the Worms," which uses the 16th century inquisitorial trial of a Friulian miller to anatomize a generally unrecorded popular mentality, one that persistently combines aspects of pagan thought with Christian ideas. He suggests that there is a remarkably long and consistent body of "low" or unlearned cultural ideas that we rarely encounter in the conventional historical record. Key aspects of that idea system are the persistence of polytheism, religious tolerance, and some other ideas that might even contest the very idea of one religion "overcoming" another.

And the book reads like a novel. Give it a shot.

In anglo saxon england lower class rural people stayed pagan for a looong time. 300 or more years there were still isolated pagan communities in different areas.

This is a great read. Long, but a great read.