Great question, and one that scholars have spent Ph.D. programs trying to explain. Because of that, I'm going to start this off suggesting a few works, and then I will dive into the answer.

There are two really friendly works that deal with this a bit. The first is From Jesus to Christianity by Michael White. It gets you about four generations out from Jesus. So really the formation of the early church. Of probably most importance though is the split from Judaism, which makes a big difference. There is a PBS documentary that White is also in that deals with a lot of the same material called From Jesus to Christ. The second word is a Great Courses Lecture by Bart Ehrman titled From Jesus to Constantine. This is more of an overview work, but it deals with the general movement from being a Jewish sect that was persecuted off an on through to being a state religion. The final source that is great is The Birth of Christianity by John Dominic Crossan. This is a less friendly work, but a classic on the subject. Like White's work, this deals more with the earliest aspect of the development on Christianity, but that helps seeing why it actually caught on.

One of the big events that the sources above cover is the destruction of the Temple in 70 CE, as part of the First Jewish Revolt. Out of this Judaism shrunk from a large variety of flavors of Judaism, to just two different sects. First, there were the Pharisees, who eventually became Rabbinical Judaism (the Judaism that exists today). The second sect was Jewish Christians, that eventually became Christianity. This is a major event that really changed the manner that both religions would go forward.

After the first Jewish War, a wedge formed between what would become Rabbinical Judaism and what would become Christianity. Without the Temple, the religions had to rethink their structure, as the Temple was the center of their religion. Rabbinical Judaism wanted to solidify Judaism under one banner, to promote a unity. Christianity was becoming more intertwined with Gentiles, and they simply ended up moving apart. The Second Jewish War would force that wedge further as Christians took a step away from the fighting as they already had a Messiah and a view of when the apocalypse would happen.

During this point, another thing began developing. In another Crossan book, Who Killed Jesus, describes the rise in polemic between Jews and Christians. This began as inter-Jewish polemic, but evolved into something new once the religion split in two. As the religions split further, what began as mostly harmless became exceptionally dangerous once Christianity gained power, and that polemic took on a new form.

This splitting was quite important as it helped Christians differentiate themselves from the Jews who were being punished after the second Jewish War. They were being seen as insurrectionists, while Christians were largely just being seen as weird. Ironically, Christianity beginning as a form of Judaism actually gave them a better reputation as Romans saw ancient traditions with added respect, and Christianity got that to begin with. After the split, and the Second Jewish War, things became different, but Christianity was already being established by that time.

So that gets us into the split between Christianity and Judaism, and how it helped Christianity get into a separate route. The spread of Christianity also helped with Christianity becoming popular. First, as we see with Paul, there was a big push to move the religion to Gentiles, and to witness to as many people as possible. Paul was not the only person doing this. Paul was just one person among many missionaries. As White, Ehrman, Crossan, and most scholars agree, the fact that there were any missionaries is somewhat of an anomaly.

Jesus wasn't the first so called Messiah (I'm using the terminology Josephus used as he documents many of these figures). He was just one among many, and generally, after they died, or were scared away, the movement they founded would end up fizzling out. For whatever reason, this didn't happen with Jesus. His brother and disciples kept up the message, and because of the nature of the message, that the end was near, it ended up pushing out missionaries. People like Paul, people who were educated and could write.

We have to put this a bit into perspective though. Wayne Meeks has a book titled The First Urban Christians, where he looks at what the first Christians would have been like. Often, when we imagine early Christians, we think of poor individuals who are one the fringes of society. As Meeks points out though is that many early Christians were educated, had some wealth (they weren't elite by any manner, but had enough money where they could put some away and even purchase meat, which was a big deal), and were somewhat well to do. Certainly, there would have been those who were destitute, but there were also quite a few that were what we could consider middle class.

Having an educated following meant that these missionaries and leaders could reach more people through letters, could argue their case in a more rationale manner, and simply spread the message more effectively.

White points out another key point though. The Roman Empire in general was undergoing massive demographic changes. This meant that the previous pagan aristocracy was dying out. So a vacuum is growing at the same time that Christianity is beginning to form and spread out from the countryside into the urban areas. Simply, they were there at the right time; it was luck. Also at around this same time (or shortly before) we have a couple of famines and plagues, which brings down the population. Christians seem to have survived at a higher rate (and not that much of a higher rate) than other demographic groups, and because of that, they go from a small minority to a larger group.

Throughout all of this, you also have a Christian message that seemed to be hitting people at a very deep level. You have all these new people moving to urban areas, where they know no one. Yet Christianity is a group that was actively reaching out and bringing people into a community, which people deeply wanted.

So what we have are a variety of factors all happening at basically the same time, that simply made it an opportune time for a religion that was missionary based to spread rapidly.

But there is one more aspect that needs to be addressed. Paula Fredriksen, in her book, From Jesus to Christ, points out an important key, and that is the Hellenistic culture. We have the Jewish Bible being translated to Greek. We have Diaspora Jewish communities, with their synagogues, throughout the Mediterranean area. These are people who speak Greek, and Christianity is able to springboard off of these communities. As Paul mentions, his way of operating was always first at the Jewish synagogue, and then out from there. These Jewish communities gave early Christians the means to travel far and wide.

What goes hand in hand with that is that at these synagogues, there were already gentiles present, who enjoyed the Jewish message, but for whatever reason, didn't fully convert. Christianity gave them a means to convert fully to a religion that they already enjoyed.

So basically, it was a perfect storm, and by the time we get Constantine, while Christianity wasn't in the majority, it was a sizable minority, and it was a lot better for Constantine to bring them into the mix.