Batı Roma İmparatorluğu hakimiyetinin kademeli olarak kaybedilmesi, yerini foederati ve Germen krallıklarının alması, çökmekte olan imparatorluk tarafından kontrol edilmeyen bölgelere yönelik erken misyonerlik çabalarıyla aynı zamana denk geldi.5. yüzyılın başlarında, Roma Britanya'sından Kelt bölgelerine (İskoçya, İrlanda ve Galler) misyonerlik faaliyetleri, daha sonra Roma'daki Kilise altında yeniden bütünleştirilen, Kelt Hristiyanlığının rakip erken geleneklerini üretti.Zamanın Kuzeybatı Avrupa'sındaki önde gelen misyonerler, Hıristiyan azizler Patrick, Columba ve Columbanus'du.Roma'nın terk edilmesinden bir süre sonra Güney Britanya'yı işgal eden Anglosakson kabileleri, başlangıçta Paganlardı, ancak Papa Büyük Gregory'nin görevi üzerine Canterbury'li Augustine tarafından Hıristiyanlığa dönüştürüldü.Kısa süre sonra bir misyonerlik merkezi haline gelen Wilfrid, Willibrord, Lullus ve Boniface gibi misyonerler, Germania'daki Sakson akrabalarını dönüştürdüler.Galya'nın (modern Fransa ve Belçika) büyük ölçüde Hıristiyan Gallo-Romen sakinleri, 5. yüzyılın başlarında Franklar tarafından istila edildi.Yerli halk, Frank Kralı I. Clovis 496'da Paganizm'den Roma Katolikliğine dönene kadar zulüm gördü. Clovis, soylu arkadaşlarının da aynı şeyi yapması konusunda ısrar etti ve yeni kurulan krallığını, yöneticilerin inancıyla yönetilenlerin inancını birleştirerek güçlendirdi.Frenk Krallığı'nın yükselişi ve istikrara kavuşan siyasi koşulların ardından, Kilise'nin Batı kesimi, sorunlu komşu halkları sakinleştirmenin bir yolu olarak Merovingian hanedanı tarafından desteklenen misyonerlik faaliyetlerini artırdı.Willibrord tarafından Utrecht'te bir kilisenin kurulmasının ardından, Pagan Frizya Kralı Radbod 716 ile 719 yılları arasında birçok Hristiyan merkezini yıktığında tepkiler meydana geldi. Almanya'da8. yüzyılın sonlarında Charlemagne, Pagan Saksonlara boyun eğdirmek ve onları zorla Hıristiyanlığı kabul etmeye zorlamak için toplu katliamlar yaptı.