הכומר יוחנן
אתיופיה

פרסטר ג'ון נחשב לשליט הודו מאז ראשית האגדה, אך "הודו" הייתה מושג מעורפל עבור האירופאים. סופרים דיברו לעיתים קרובות על "שלוש הודו" אך היו חסרים כל ידיעה אמיתית על האוקיינוס ההודי, הם חשבו לעיתים את אתיופיה כאחד מהשלושה. מערביים ידעו כי אתיופיה היא אומה נוצרית רבת עוצמה, אך הקשר היה ספורדי מאז עליית האסלאם. שום פרסטר ג'ון לא ניתן היה למצוא באסיה, ולכן הדמיון האירופי הניע אותו סביב הגבולות המטושטשים של "הודו" עד שמצאה עבורו ממלכה חזקה כראוי באתיופיה. עדויות הראו כי איתור ממלכתו של פרסטר ג'ון באתיופיה נכנס לתודעה הקולקטיבית בסביבות 1250.
מרקו פולו דן באתיופיה כארץ נוצרית מפוארת ולנוצרים אורתודוקסים הייתה אגדה שהאומה תקום יום אחד ותפלוש לערב אך הם לא מיקמו שם את פרסטר ג'ון. בשנת 1306 הגיעו לאירופה 30 שגרירים אתיופים מהקיסר וודם ארד, ופרסטר ג'ון הוזכר כפטריארך של הכנסייה שלהם ברשומה של ביקורם. תיאור נוסף של כהן אפריקני ג'ון נמצא בספר 'מיראביליה דקריפטה' של המיסיונר הדומיניקני יורדנוס, בסביבות 1329. בדיון ב"הודו השלישית ", יורדנוס מתעד מספר סיפורים מפוארים על הארץ ומלכה, שלדבריו האירופאים מכנים אותו פרסטר ג'ון.
לאחר זמן זה, המיקום האפריקני הפך לפופולרי יותר ויותר. ייתכן שהדבר נבע מגידול הקשרים בין אירופה לאפריקה, כאשר בשנת 1428 מלכי אראגון ואתיופיה ניהלו משא ומתן באופן פעיל על אפשרות לנישואין אסטרטגיים בין שתי הממלכות. ב־7 במאי 1487 נשלחו שני שליחים פורטוגזים, פרו דה קובילה ואפונסו דה פאיבה, שנסעו בחשאי על פני היבשה כדי לאסוף מידע על נתיב ימי אפשרי להודו, אך גם לברר על פרסטר ג'ון. קובילה הצליח להגיע לאתיופיה. אף על פי שהתקבל יפה, נאסר עליו לצאת. שליחים נוספים נשלחו בשנת 1507, לאחר שהאי סוקוטרה נכבש על ידי הפורטוגזים. כתוצאה ממשימה זו, וכנגד התפשטות מוסלמית, שלחה המלכה הלני מאתיופיה את מטאוס כשליח למלך מנואל הראשון מפורטוגל ולאפיפיור בחיפוש אחר קואליציה. מטאוס הגיע לפורטוגל דרך גואה, יחד עם הכומר פרנסיסקו אלווארס בשנת 1520. ספרו של פרנסיסקו אלווארס, שכלל את עדותו של קובילה, היה התיאור הישיר הראשון של אתיופיה, והגדיל מאוד את הידע האירופי באותה עת, כפי שהוצג לאפיפיור, שפורסם וצוטט על ידי ג'ובאני בטיסטה ראמוסיו.
עד שהקיסר לבנה דינגל והפורטוגלים יצרו קשר דיפלומטי זה עם זה בשנת 1520, היה פרסטר ג'ון השם שבאמצעותו הכירו האירופאים את הקיסר של אתיופיה. האתיופים, עם זאת, מעולם לא כינו את הקיסר שלהם כך. כששגרירים מהקיסר זרע יעקב השתתפו במועצת פירנצה בשנת 1441, הם היו מבולבלים כשאנשי המועצה התעקשו להתייחס למלך שלהם ככומר ג'ון. הם ניסו להסביר כי בשום מקום ברשימת השמות הממלכתיים של זרע יעקב לא מצוי כינוי כזה למלך. עם זאת, ההצהרות שלהם לא מנעו מהאירופאים לקרוא למלך אתיופיה פרסטר ג'ון. חלק מהכותבים שהשתמשו בכנוי הבינו שלא מדובר בשם ילידי אתיופי.
אתיופיה נטען במשך שנים רבות היא המקור לאגדת פרסטר ג'ון, אך מרבית המומחים המודרניים מאמינים כי האגדה פשוט הותאמה כך שתתאים לאומה האתיופית באותה צורה שהיא הותאמה על אונג חאן ומרכז אסיה במהלך המאה ה-13. חוקרים מודרניים לא מוצאים דבר על פרסטר ג'ון או ארצו בטקסטים מוקדמים שיהפוך את אתיופיה לזיהוי מתאים יותר מכל מקום אחר. יתרה מכך, מומחים בהיסטוריה של אתיופיה הוכיחו כי הסיפור לא היה מוכר שם בהרחבה עד לאחר שנוצר הקשר האירופי. הפרנציסקני צ'מדי רמדיוס פרוטקי שאל את הקיסר אייאסו השני על כך בשנת 1751, ופרוטקי קובע כי האיש "נדהם, ואמר לי שמלכי אטיופיה מעולם לא היו רגילים לקרוא לעצמם בשם הזה". בהערת שוליים לקטע זה, ריצ'רד פנקהורסט קובע כי זו ככל הנראה ההצהרה המתועדת הראשונה של המלוכה האתיופית על סיפור הכומר, וככל הנראה לא היו מודעים לתואר עד לבירורו של פרוטקי.