Länsi-Rooman valtakunnan asteittainen menetys, joka korvattiin foederati- ja germaanisilla valtakunnilla, osui samaan aikaan varhaisten lähetystyön kanssa alueille, joita romahtava valtakunta ei hallitse.Jo 500-luvulla lähetystyö Roomalaisesta Britanniasta kelttiläisille alueille (Skotlanti, Irlanti ja Wales) tuotti kilpailevia varhaisia ​​kelttikristillisyyden perinteitä, jotka myöhemmin yhdistettiin Rooman kirkon alaisuuteen.Tunnettuja lähetyssaarnaajia Luoteis-Euroopassa tuolloin olivat kristityt pyhät Patrick, Columba ja Columbanus.Anglosaksiset heimot, jotka hyökkäsivät Etelä-Britanniaan jonkin aikaa Rooman hylkäämisen jälkeen, olivat alun perin pakanoita, mutta Augustinus Canterburylainen käänsi heidät kristinuskoon paavi Gregorius Suuren tehtävässä.Pian lähetystyökeskukseksi tulleet lähetyssaarnaajat, kuten Wilfrid, Willibrord, Lullus ja Boniface, käänsivät saksalaiset sukulaisensa Germaniaan.Frankit valtasivat Gallian (nykyisen Ranskan ja Belgian) pääosin kristityt gallo-roomalaiset asukkaat 500-luvun alussa.Alkuperäisiä asukkaita vainottiin, kunnes frankkien kuningas Clovis I kääntyi pakanuudesta roomalaiskatolisuuteen vuonna 496. Clovis vaati, että hänen aatelistoverinsa seurasivat esimerkkiä ja vahvisti äskettäin perustettua valtakuntaansa yhdistämällä hallitsijoiden uskon hallittujen uskon kanssa.Frankin kuningaskunnan nousun ja vakiintuneiden poliittisten olosuhteiden jälkeen kirkon länsiosa lisäsi lähetystyötä Merovingien dynastian tukemana keinona rauhoittaa hankaluuksia naapurikansoja.Willibrordin Utrechtiin kirkon perustamisen jälkeen tapahtui vastareaktioita, kun pakanallinen friisiläinen kuningas Radbod tuhosi monia kristillisiä keskuksia vuosina 716–719. Vuonna 717 englantilainen lähetyssaarnaaja Bonifatius lähetettiin auttamaan Willibrordia, perustamaan uudelleen kirkkoja Friisiläiselle alueelle ja jatkamaan lähetystöitä. Saksassa .800-luvun lopulla Kaarle Suuri käytti joukkomurhia alistaakseen pakanalliset saksit ja pakottaakseen heidät hyväksymään kristinuskon.