Hilangnya dominasi Kekaisaran Romawi Barat secara bertahap, digantikan dengan kerajaan foederati dan Jermanik, bertepatan dengan upaya misionaris awal ke daerah-daerah yang tidak dikendalikan oleh kekaisaran yang runtuh.Pada awal abad ke-5, kegiatan misionaris dari Inggris Romawi ke wilayah Celtic (Skotlandia, Irlandia, dan Wales) menghasilkan tradisi awal Kekristenan Celtic yang saling bersaing, yang kemudian diintegrasikan kembali di bawah Gereja di Roma.Misionaris terkemuka di Eropa Barat Laut saat itu adalah orang-orang kudus Kristen Patrick, Columba, dan Columbanus.Suku-suku Anglo-Saxon yang menginvasi Inggris Selatan beberapa saat setelah Romawi ditinggalkan pada awalnya adalah kaum Pagan tetapi diubah menjadi Kristen oleh Agustinus dari Canterbury atas misi Paus Gregorius Agung.Segera menjadi pusat misionaris, misionaris seperti Wilfrid, Willibrord, Lullus, dan Boniface mempertobatkan kerabat Saxon mereka di Germania.Penduduk Gallo-Romawi yang sebagian besar beragama Kristen di Gaul ( Prancis dan Belgia modern) dikuasai oleh kaum Frank pada awal abad ke-5.Penduduk asli dianiaya sampai Frankish King Clovis I berpindah dari Paganisme ke Katolik Roma pada tahun 496. Clovis bersikeras agar sesama bangsawan mengikutinya, memperkuat kerajaannya yang baru didirikan dengan menyatukan keyakinan para penguasa dengan yang diperintah.Setelah kebangkitan Kerajaan Frank dan kondisi politik yang stabil, Gereja bagian Barat meningkatkan kegiatan misionaris, didukung oleh dinasti Merovingian sebagai sarana untuk menenangkan masyarakat tetangga yang menyusahkan.Setelah pendirian sebuah gereja di Utrecht oleh Willibrord, serangan balik terjadi ketika Raja Frisia Radbod yang Pagan menghancurkan banyak pusat Kristen antara tahun 716 dan 719. Pada tahun 717, misionaris Inggris Bonifasius dikirim untuk membantu Willibrord, mendirikan kembali gereja di Frisia dan melanjutkan misi di Jerman .Selama akhir abad ke-8, Charlemagne menggunakan pembunuhan massal untuk menaklukkan Pagan Saxon dan memaksa mereka untuk menerima agama Kristen.