Ang sunud-sunod na pagkawala ng Western Roman Empire dominasyon, na pinalitan ng foederati at Germanic na mga kaharian, ay kasabay ng maagang pagsisikap ng mga misyonero sa mga lugar na hindi kontrolado ng gumuhong imperyo.Noong ika-5 siglo, ang mga gawaing misyonero mula sa Roman Britain patungo sa mga lugar ng Celtic (Scotland, Ireland, at Wales) ay nagbunga ng mga nakikipagkumpitensya na sinaunang tradisyon ng Celtic Christianity, na kalaunan ay muling pinagsama sa ilalim ng Simbahan sa Roma.Ang mga kilalang misyonero sa Northwestern Europe noong panahong iyon ay ang mga Kristiyanong santo na sina Patrick, Columba, at Columbanus.Ang mga tribong Anglo-Saxon na sumalakay sa Timog Britain ilang panahon pagkatapos ng pag-abandona ng mga Romano ay mga Pagano sa simula ngunit na-convert sa Kristiyanismo ni Augustine ng Canterbury sa misyon ni Pope Gregory the Great.Di-nagtagal ay naging sentro ng misyonero, ang mga misyonero tulad nina Wilfrid, Willibrord, Lullus, at Boniface ay nagbalik-loob sa kanilang mga kamag-anak na Saxon sa Germania.Ang karamihan sa mga Kristiyanong Gallo-Roman na naninirahan sa Gaul (modernong France at Belgium) ay nasakop ng mga Frank noong unang bahagi ng ika-5 siglo.Ang mga katutubong naninirahan ay pinag-usig hanggang sa ang Frankish na si Haring Clovis I ay nagbalik-loob mula sa Paganismo tungo sa Romano Katolisismo noong 496. Iginiit ni Clovis na sundin ito ng kanyang mga kapwa maharlika, anupat pinalalakas ang kanyang bagong tatag na kaharian sa pamamagitan ng pagsasama-sama ng pananampalataya ng mga pinuno sa pinamumunuan.Matapos ang pag-usbong ng Frankish Kingdom at ang nagpapatatag na mga kalagayang pampulitika, ang Kanluraning bahagi ng Simbahan ay nagpalaki ng mga gawaing misyonero, na suportado ng dinastiyang Merovingian bilang isang paraan upang patahimikin ang mga magulong kapitbahay.Matapos ang pundasyon ng isang simbahan sa Utrecht ni Willibrord, naganap ang mga backlashes nang sirain ng Pagan Frisian King Radbod ang maraming sentrong Kristiyano sa pagitan ng 716 at 719. Noong 717, ipinadala ang English missionary na si Boniface upang tulungan si Willibrord, muling itatag ang mga simbahan sa Frisia at ipagpatuloy ang mga misyon. sa Germany .Noong huling bahagi ng ika-8 siglo, ginamit ni Charlemagne ang malawakang pagpatay upang sakupin ang Pagan Saxon at pilitin silang tanggapin ang Kristiyanismo.