Het stapsgewijze verlies van de dominantie van het West-Romeinse rijk, vervangen door foederati en Germaanse koninkrijken, viel samen met vroege missionaire inspanningen in gebieden die niet werden gecontroleerd door het ineenstortende rijk.Al in de 5e eeuw brachten missionaire activiteiten vanuit Romeins Groot-Brittannië naar de Keltische gebieden (Schotland, Ierland en Wales) concurrerende vroege tradities van het Keltische christendom voort, dat later opnieuw werd geïntegreerd onder de kerk in Rome.Prominente missionarissen in Noordwest-Europa van die tijd waren de christelijke heiligen Patrick, Columba en Columbanus.De Angelsaksische stammen die enige tijd na de Romeinse verlatenheid Zuid-Brittannië binnenvielen, waren aanvankelijk heidenen, maar werden tot het christendom bekeerd door Augustinus van Canterbury op de missie van paus Gregorius de Grote.Missionarissen zoals Wilfrid, Willibrord, Lullus en Bonifatius werden al snel een missionariscentrum en bekeerden hun Saksische familieleden in Germania.De grotendeels christelijke Gallo-Romeinse inwoners van Gallië (het huidige Frankrijk en België) werden in het begin van de 5e eeuw onder de voet gelopen door de Franken.De inheemse bewoners werden vervolgd totdat de Frankische koning Clovis I zich in 496 bekeerde van het heidendom tot het rooms-katholicisme. Clovis stond erop dat zijn mede-edelen dit voorbeeld volgden en zijn nieuw opgerichte koninkrijk versterkte door het geloof van de heersers te verenigen met dat van de overheersten.Na de opkomst van het Frankische koninkrijk en de stabiliserende politieke omstandigheden, verhoogde het westelijke deel van de kerk de missionaire activiteiten, ondersteund door de Merovingische dynastie als een middel om lastige buurvolken tot bedaren te brengen.Na de stichting van een kerk in Utrecht door Willibrord, ontstond er verzet toen de heidense Friese koning Radbod tussen 716 en 719 veel christelijke centra verwoestte. In 717 werd de Engelse missionaris Boniface gestuurd om Willibrord te helpen, kerken in Friesland te herstellen en missies voort te zetten in Duitsland .Aan het einde van de 8e eeuw gebruikte Karel de Grote massamoorden om de heidense Saksen te onderwerpen en hen met geweld te dwingen het christendom te aanvaarden.