האובדן המדרגתי של הדומיננטיות של האימפריה הרומית המערבית, שהוחלף בממלכות פודראטיות וממלכות גרמניות, עלה בקנה אחד עם מאמצי המיסיון המוקדמים לאזורים שאינם בשליטת האימפריה הקורסת.כבר במאה ה-5, פעילות מיסיונרית מבריטניה הרומית לתוך האזורים הקלטים (סקוטלנד, אירלנד ווילס) יצרה מסורות מוקדמות מתחרות של הנצרות הקלטית, ששולבה מאוחר יותר תחת הכנסייה ברומא.מיסיונרים בולטים בצפון מערב אירופה באותה תקופה היו הקדושים הנוצרים פטריק, קולומבה וקולומבנוס.השבטים האנגלו-סכסיים שפלשו לדרום בריטניה זמן מה לאחר נטישת הרומאים היו בתחילה עובדי אלילים אך הומרו לנצרות על ידי אוגוסטינוס מקנטרברי בשליחות האפיפיור גרגוריוס הגדול.עד מהרה הפכו למרכז מיסיונרים, מיסיונרים כמו וילפריד, ויליברורד, לולוס ובוניפאס המירו את קרוביהם הסקסונים בגרמניה.התושבים הגאלו-רומיים הנוצרים ברובם של גאליה ( צרפת ובלגיה המודרנית) הוכרעו על ידי הפרנקים בתחילת המאה ה-5.התושבים הילידים נרדפו עד שהמלך הפרנקי קלוביס הראשון המיר את דתו מפגאניזם לקתוליות הרומית בשנת 496. קלוביס התעקש שחבריו האצילים ילכו בעקבותיו, וחיזקו את ממלכתו החדשה שהוקמה על ידי איחוד אמונת השליטים עם זו של הנשלטים.לאחר עליית הממלכה הפרנקית והתנאים הפוליטיים המייצבים, הגביר החלק המערבי של הכנסייה את הפעילות המיסיונרית, בתמיכת השושלת המרובינגית כאמצעי להרגעת עמים שכנים מטרידים.לאחר הקמתה של כנסייה באוטרכט על ידי ויליברורד, התרחשו תגובות נגד כאשר המלך הפריזאי הפגאני רדבוד הרס מרכזים נוצריים רבים בין השנים 716 ל-719. בשנת 717, המיסיונר האנגלי בוניפאסי נשלח לסייע לוויליברורד, הקים מחדש כנסיות בפריזיה והמשיך בשליחות. בגרמניה .במהלך סוף המאה ה-8, קרל הגדול השתמש בהרג המוני על מנת להכניע את הסקסונים הפגאנים ולאלץ אותם בכוח לקבל את הנצרות.