The stepwise loss of Western Roman Empire dominance, replaced with foederati and Germanic kingdoms, coincided with early missionary efforts into areas not controlled by the collapsing empire. As early as in the 5th century, missionary activities from Roman Britain into the Celtic areas (Scotland, Ireland, and Wales) produced competing early traditions of Celtic Christianity, that was later reintegrated under the Church in Rome. Prominent missionaries in Northwestern Europe of the time were the Christian saints Patrick, Columba, and Columbanus. The Anglo-Saxon tribes that invaded Southern Britain some time after the Roman abandonment were initially Pagans but were converted to Christianity by Augustine of Canterbury on the mission of Pope Gregory the Great. Soon becoming a missionary centre, missionaries such as Wilfrid, Willibrord, Lullus, and Boniface converted their Saxon relatives in Germania.

The largely Christian Gallo-Roman inhabitants of Gaul (modern France and Belgium) were overrun by the Franks in the early 5th century. The native inhabitants were persecuted until the Frankish King Clovis I converted from Paganism to Roman Catholicism in 496. Clovis insisted that his fellow nobles follow suit, strengthening his newly established kingdom by uniting the faith of the rulers with that of the ruled. After the rise of the Frankish Kingdom and the stabilizing political conditions, the Western part of the Church increased the missionary activities, supported by the Merovingian dynasty as a means to pacify troublesome neighbour peoples. After the foundation of a church in Utrecht by Willibrord, backlashes occurred when the Pagan Frisian King Radbod destroyed many Christian centres between 716 and 719. In 717, the English missionary Boniface was sent to aid Willibrord, re-establishing churches in Frisia and continuing missions in Germany. During the late 8th century, Charlemagne used mass killings in order to subjugate the Pagan Saxons and forcibly compel them to accept Christianity.