Stopniowa utrata dominacji zachodniego imperium rzymskiego, zastąpiona królestwami foederati i germańskimi, zbiegła się w czasie z wczesnymi wysiłkami misyjnymi na obszarach nie kontrolowanych przez upadające imperium.Już w V wieku działalność misyjna z rzymskiej Brytanii na tereny celtyckie (Szkocja, Irlandia i Walia) stworzyła konkurencyjne wczesne tradycje chrześcijaństwa celtyckiego, które później zostało ponownie zintegrowane w ramach Kościoła w Rzymie.Wybitnymi misjonarzami w północno-zachodniej Europie tamtych czasów byli chrześcijańscy święci Patryk, Kolumba i Kolumban.Plemiona anglosaskie , które najechały południową Brytanię jakiś czas po opuszczeniu przez Rzymian, były początkowo poganami, ale zostały nawrócone na chrześcijaństwo przez Augustyna z Canterbury na misję papieża Grzegorza Wielkiego.Wkrótce stając się ośrodkiem misyjnym, misjonarze tacy jak Wilfrid, Willibrord, Lullus i Bonifacy nawrócili swoich saksońskich krewnych w Germanii.W większości chrześcijańscy galijsko-rzymscy mieszkańcy Galii (współczesna Francja i Belgia) zostali opanowani przez Franków na początku V wieku.Rdzenni mieszkańcy byli prześladowani do czasu, gdy król Franków Clovis I nawrócił się z pogaństwa na katolicyzm w 496 roku. Clovis nalegał, aby jego koledzy ze szlachty poszli w jego ślady, wzmacniając jego nowo utworzone królestwo, łącząc wiarę władców z wiarą rządzonych.Po powstaniu Królestwa Franków i ustabilizowaniu się warunków politycznych zachodnia część Kościoła zintensyfikowała działalność misyjną, wspieraną przez dynastię Merowingów, jako sposób na pacyfikację kłopotliwych ludów sąsiednich.Po założeniu kościoła w Utrechcie przez Willibrorda, doszło do luzów, gdy pogański król Fryzji Radbod zniszczył wiele ośrodków chrześcijańskich w latach 716-719. W 717 roku angielski misjonarz Bonifacy został wysłany na pomoc Willibrordowi, przywracając kościoły we Fryzji i kontynuując misje w Niemczech .Pod koniec VIII wieku Karol Wielki dokonał masowych mordów, aby ujarzmić pogańskich Sasów i siłą zmusić ich do przyjęcia chrześcijaństwa.