Everyone who is at least vaguely familiar with the history of Christianity and the Roman Empire knows the story. The emperor Constantine, shortly before engaging his rival Maxentius at the Battle of Milvian Bridge in the year 312, allegedly saw a vision in the sky of the Christian Cross above the words "In Hoc Signo Vinces", Latin for "by this sign, conquer." As the story goes, Constantine had his soldiers mark their shields with the sign of the cross, and they proceeded to defeat Maxentius. Constantine afterwards issued the Edict of Milan, officially putting an end to the persecution of Christians that had reached a crescendo under the reign of his predecessor Diocletian. From there onwards, Christianity embarked on what in hindsight seems to have been its inevitable march from a recognized faith in the empire to the official faith of the empire, the brief speedbump that was Julian's reign notwithstanding.
Constantine's victory and embrace of Christianity, while a major milestone in the history of the religion, was the first of what would prove to be a recognizeable pattern in the rise of the faith into the early Middle Ages. In other words, the spread of the teachings of Jesus Christ owed a great deal to emperors and kings being victorious in battles that resulted in the deaths of other people.
In the wake of the disintegration of the Western Empire in the latter half of the fifth century (which some people mistakenly attribute to Christianity itself), the Catholic Church was the only "Roman" institution that remained. In order for the Church to survive and prosper, it needed the Germanic kings who occupied the former Roman territories to convert to Christianity and be baptized in the Church. Filling the power vacuum left by the collapse of Roman authority in Gaul (modern day France) was the kingdom of the Franks under its aggressively expansionist ruler Clovis.
While the wife of Clovis was a Catholic, Clovis himself was not quite prepared at first to take the plunge. Then, in the thick of battle against the Alamanni in the year 496, Clovis is said to have called upon Jesus Christ and promised to to be baptized if he was victorious. As it turned out, Clovis won the battle and eventually fulfilled his promise to be baptized. His decision was momentous not only for Christianity in general, but for Catholicism in particular, as at that time in history the Catholic Church was in competition with what it deemed to be the heresy of Arianism.
The story would repeat itself in post-Roman Britain. From Richard Fletcher's The Barbarian Conversions, "The contemporary written sources bearing upon the conversion of kings prompt reflection on a number of themes. First, we observe the repeated assurance that acceptance of Christianity will bring victory, wide dominion, fame and riches. This is what Germanic kings wanted to hear, because their primary activity was war." (Text bolded for emphasis)
From the standpoint of the Church, in order to be able to proselytize in a given territory, it needed to curry the favor of the local ruler. If a warrior king could be convinced that his success in battle was due to the support of the Christian god, then that king would allow himself to be baptized and encourage his subjects to follow suit. And struggles with neighboring pagan kings would not simply be a conflict over territory or wealth, but literally a war between the forces of good and evil.
Prior to Constantine's victory at Milvian Bridge, Christianity was more of a grassroots movement. It spread and gained adherents in spite of the position of the Roman government. But from Constantine onward, Christianity became an instrument of state policy. Thus, with the disintegration of Roman governmental authority in Western Europe, the Church sought to continue this pattern by marrying itself to the barbarian kings, which in turn paved the way for spreading the faith to their subjects. What started out as a faith that spread from the bottom-up had turned into a top-down affair that relied on good, old fashioned brute force.