Christianity wouldn't have spread nearly as quickly or as far if it hadn't been able to piggyback on the Roman Empire's infrastructure. On the flip side, after Rome's political influence left most of Europe, the parallel church structure was still there to help maintain civilization at least a little bit during the barbarian invasions and general collapse.

[Leaving out Mithraism, which also spread in similar ways, as well as any discussion of what exactly constitutes "barbarian" vs. "civilization" since it gets fuzzier the closer you look.]