Det trinnvise tapet av Vestromerrikets dominans, erstattet med foederati og germanske riker, falt sammen med tidlig misjonsinnsats i områder som ikke var kontrollert av det kollapsende imperiet.Så tidlig som på 500-tallet ga misjonsaktiviteter fra romerske Storbritannia til de keltiske områdene (Skottland, Irland og Wales) konkurrerende tidlige tradisjoner for keltisk kristendom, som senere ble reintegrert under kirken i Roma.Fremtredende misjonærer i Nordvest-Europa på den tiden var de kristne helgenene Patrick, Columba og Columbanus.De angelsaksiske stammene som invaderte Sør- Storbritannia en tid etter den romerske forlatelsen var opprinnelig hedninger, men ble konvertert til kristendommen av Augustine av Canterbury på oppdrag fra pave Gregor den store.Etter å ha blitt et misjonssenter, konverterte misjonærer som Wilfrid, Willibrord, Lullus og Boniface sine saksiske slektninger i Germania.De stort sett kristne gallo-romerske innbyggerne i Gallia (det moderne Frankrike og Belgia) ble overkjørt av frankerne på begynnelsen av 400-tallet.De innfødte innbyggerne ble forfulgt inntil den frankiske kong Clovis I konverterte fra hedendom til romersk-katolisisme i 496. Clovis insisterte på at hans medadelsmenn fulgte etter, og styrket hans nyetablerte rike ved å forene troen til herskerne med de styrte.Etter fremveksten av det frankiske riket og de stabiliserende politiske forholdene, økte den vestlige delen av kirken misjonsvirksomheten, støttet av det merovingerske dynastiet som et middel til å berolige plagsomme nabofolk.Etter grunnleggelsen av en kirke i Utrecht av Willibrord, oppsto tilbakeslag da den hedenske frisiske kong Radbod ødela mange kristne sentre mellom 716 og 719. I 717 ble den engelske misjonæren Boniface sendt for å hjelpe Willibrord, gjenopprette kirker i Frisia og fortsette misjonen i Tyskland .I løpet av slutten av 800-tallet brukte Charlemagne massedrap for å underlegge de hedenske sakserne og tvinge dem til å akseptere kristendommen.