Η σταδιακή απώλεια της κυριαρχίας της Δυτικής Ρωμαϊκής Αυτοκρατορίας, που αντικαταστάθηκε με βασίλεια φοεντεράτι και γερμανικά, συνέπεσε με τις πρώτες ιεραποστολικές προσπάθειες σε περιοχές που δεν ελέγχονταν από την καταρρέουσα αυτοκρατορία.Ήδη από τον 5ο αιώνα, οι ιεραποστολικές δραστηριότητες από τη Ρωμαϊκή Βρετανία στις κελτικές περιοχές (Σκωτία, Ιρλανδία και Ουαλία) παρήγαγαν ανταγωνιστικές πρώιμες παραδόσεις του Κελτικού Χριστιανισμού, ο οποίος αργότερα επανενσωματώθηκε στην Εκκλησία της Ρώμης.Εξέχοντες ιεραπόστολοι στη Βορειοδυτική Ευρώπη της εποχής ήταν οι χριστιανοί άγιοι Πάτρικ, Κολούμπα και Κολομπάνος.Οι αγγλοσαξονικές φυλές που εισέβαλαν στη Νότια Βρετανία λίγο μετά τη ρωμαϊκή εγκατάλειψη ήταν αρχικά ειδωλολάτρες, αλλά μετατράπηκαν στον Χριστιανισμό από τον Αυγουστίνο του Καντέρμπουρυ με αποστολή του Πάπα Γρηγορίου του Μεγάλου.Σύντομα έγιναν ιεραποστολικό κέντρο, ιεραπόστολοι όπως ο Wilfrid, ο Willibrord, ο Lullus και ο Boniface προσηλυτίστηκαν στους Σάξονες συγγενείς τους στη Γερμανία.Οι σε μεγάλο βαθμό χριστιανοί Γαλλο-Ρωμαίοι κάτοικοι της Γαλατίας (σημερινή Γαλλία και Βέλγιο) κατακλύστηκαν από τους Φράγκους στις αρχές του 5ου αιώνα.Οι γηγενείς κάτοικοι διώκονταν έως ότου ο Φράγκος βασιλιάς Κλόβις Α' μεταστράφηκε από τον παγανισμό σε ρωμαιοκαθολικισμό το 496. Ο Κλόβις επέμενε να ακολουθήσουν το παράδειγμά τους οι συνάδελφοί του ευγενείς, ενισχύοντας το νεοσύστατο βασίλειό του ενώνοντας την πίστη των ηγεμόνων με αυτή των κυβερνωμένων.Μετά την άνοδο του Φραγκικού Βασιλείου και τις σταθεροποιούμενες πολιτικές συνθήκες, το δυτικό τμήμα της Εκκλησίας αύξησε τις ιεραποστολικές δραστηριότητες, υποστηριζόμενες από τη δυναστεία των Μεροβίγγεων ως μέσο ειρήνευσης των ενοχλητικών γειτονικών λαών.Μετά την ίδρυση μιας εκκλησίας στην Ουτρέχτη από τον Willibrord, υπήρξαν αντιδράσεις όταν ο Παγανός Φριζός βασιλιάς Radbod κατέστρεψε πολλά χριστιανικά κέντρα μεταξύ 716 και 719. Το 717, ο Άγγλος ιεραπόστολος Βονιφάτιος στάλθηκε για να βοηθήσει τον Willibrord, ξαναδημιουργώντας εκκλησίες στη Frisia και συνεχίζοντας τις αποστολές στη Γερμανία .Στα τέλη του 8ου αιώνα, ο Καρλομάγνος χρησιμοποίησε μαζικές δολοφονίες για να υποτάξει τους ειδωλολάτρες Σάξονες και να τους εξαναγκάσει να δεχτούν τον Χριστιανισμό.