Постепенната загуба на господството на Западната Римска империя, заменена с федерати и германски кралства, съвпада с ранните мисионерски усилия в области, които не се контролират от рухващата империя.Още през 5-ти век мисионерските дейности от римска Британия в келтските области (Шотландия, Ирландия и Уелс) създават конкуриращи се ранни традиции на келтското християнство, което по-късно е реинтегрирано под Църквата в Рим.Видни мисионери в Северозападна Европа от онова време са християнските светци Патрик, Колумба и Колумбан.Англосаксонските племена, които нахлуха в Южна Британия известно време след изоставянето на Рим, първоначално бяха езичници, но бяха обърнати в християнството от Августин Кентърбърийски по мисията на папа Григорий Велики.Скоро ставайки мисионерски център, мисионери като Уилфрид, Уилиброрд, Лулус и Бонифаций обръщат своите саксонски роднини в Германия.До голяма степен християнските гало-римски жители на Галия (съвременна Франция и Белгия) са превзети от франките в началото на 5 век.Местните жители са преследвани, докато франкският крал Кловис I не се обръща от езичеството към римокатолицизма през 496 г. Кловис настоява колегите му благородници да последват примера, укрепвайки новосъздаденото си кралство чрез обединяване на вярата на управляващите с тази на управляваните.След възхода на Франкското кралство и стабилизиращите се политически условия, западната част на Църквата увеличи мисионерските дейности, подкрепяни от династията на Меровингите като средство за умиротворяване на проблемните съседни народи.След основаването на църква в Утрехт от Уилиброрд, възникнаха обратни реакции, когато езическият фризийски крал Радбод унищожи много християнски центрове между 716 и 719 г. През 717 г. английският мисионер Бонифаций беше изпратен да помогне на Уилиброрд, възстановявайки църкви във Фризия и продължавайки мисиите в Германия .В края на 8 век Карл Велики използва масови убийства, за да подчини езическите саксонци и насилствено да ги принуди да приемат християнството.