Postepeni gubitak dominacije Zapadnog Rimskog Carstva, zamijenjen foederati i germanskim kraljevstvima, koincidirao je s ranim misionarskim naporima u područjima koja nisu bila pod kontrolom carstva u raspadu.Još u 5. stoljeću, misionarske aktivnosti iz rimske Britanije u keltska područja (Škotska, Irska i Wales) proizvele su konkurentske rane tradicije keltskog kršćanstva, koje je kasnije reintegrirano pod Crkvom u Rimu.Istaknuti misionari u sjeverozapadnoj Europi toga doba bili su kršćanski sveci Patrik, Columba i Columbanus.Anglosaksonska plemena koja su napala južnu Britaniju neko vrijeme nakon napuštanja Rimljana u početku su bila pogani, ali ih je Augustin od Canterburyja obratio na kršćanstvo u misiji pape Grgura Velikog.Ubrzo postajući misionarsko središte, misionari poput Wilfrida, Willibrorda, Lullusa i Bonifacija preobratili su svoje saske rođake u Njemačkoj.Uglavnom kršćanske galo-rimske stanovnike Galije (moderna Francuska i Belgija) pregazili su Franci početkom 5. stoljeća.Domaće stanovništvo bilo je progonjeno sve dok se franački kralj Klodvig I nije obratio s poganstva na rimokatolicizam 496. Klodvig je inzistirao da njegovi kolege plemići slijede njegov primjer, jačajući svoje novoosnovano kraljevstvo ujedinjujući vjeru vladara s vjerom onih kojima se vlada.Nakon uspona Franačkog kraljevstva i stabilizacije političkih uvjeta, zapadni dio Crkve povećao je misionarske aktivnosti, koje je podupirala dinastija Merovinga kao sredstvo za smirivanje problematičnih susjednih naroda.Nakon što je Willibrord osnovao crkvu u Utrechtu, došlo je do negativnih reakcija kada je poganski frizijski kralj Radbod uništio mnoga kršćanska središta između 716. i 719. Godine 717. engleski misionar Bonifacije poslan je da pomogne Willibrordu, ponovno uspostavljajući crkve u Friziji i nastavljajući misije u Njemačkoj .Tijekom kasnog 8. stoljeća, Karlo Veliki se služio masovnim ubojstvima kako bi pokorio poganske Saksonce i nasilno ih prisilio da prihvate kršćanstvo.