מרומא המשיך בנימין לקפואה אותה תיאר "והיא טובה אבל המים רעים וארץ משכלת", וממנה לעיר המרפא פוצולי שעל חוף קמפניה, ומשם הגיע לנאפולי. ערי קמפניה, קפואה פוצולי ונאפולי, היו ערים מיושבות ביהודים רבים יותר מאשר בצפון איטליה, ובה נכרכו אגדות רבות סביב מונומנטים היסטוריים וקשירתם במעשים תנ"כיים. כך מתאר בנימין את ארמונו של הדדעזר אויבו של דוד המלך בפוצולי, ומנהרות שחפרו רמוס ורומולוס במלחמותיהם בדוד המלך.
מנאפולי החל בנימין מטודלה במסעו דרום-מזרחה לכיוון נמל אוטרנטו שבקצה איטליה, כשבדרכו הוא עובר בבנוונטו שבקמפניה, אסקולי סטריאנו, בארי, טאראנטו וברינדיזי שבפוליה אותה חשב ל"ארץ פול" התנ"כית. בערים אלו היו קהילות יהודיות גדולות ומבוססות, ובנימין הגיע לברינדיזי, בה התגוררו כעשרה יהודים שעסקו בצביעה, וממנה לאוטרנטו, על חוף מצר אוטרנטו ובקצה ארץ המגף.
יוון, הבלקן, איי הים התיכון.
מאוטרנטו הפליג בנימין לקורפו, בה ישב באותה עת יהודי אחד בלבד, והייתה קצה ממלכת סיציליה. משם הפליג בנימין ליוון, והגיע לארטה. מארטה נסע בנימין דרומה לכיוון פטרס, דרך אפילון ונטוליקון, ומפטרס המשיך וביקר בנאופקטוס הסמוכה (אותה כינה בכינויה הספרדי "לפנטו"). הוא המשיך במסעו מזרחה לאורך צפונו של מפרץ קורינתוס עד לעיר קורינתוס, ומשם שב צפונה אל תבאי.
בתבאי, העיר היוונית העתיקה, פגש בנימין קהילה יהודית גדולה ותוססת. הוא מתאר את חכמי העיר היהודים: "והם האומנים הטובים לעשות בגדי משי וארגמן בארץ היוונים, ובהם חכמים גדולים במשנה ובתלמוד, והם גדולי הדור ובראשם הרב הגדול רבי קוטי ורבי משה אחריו ורבי חייא ורבי אליה תורתינו ורבי יקטן, ואין כמוהם בכל ארץ יוון חוץ ממדינת קונטשטנטינופולי".
מתבאי המשיך בנימין במסעו צפונה. הוא עבר בכלקיס ובערי צפון יוון עד שהגיע לסלוניקי, וממנה נסע מזרחה דרך דימיטריזי, דרמה, קריסטופולי ואבידוס אל קונסטנטינופול. בספרו של בנימין השתמר תיאור הפחד שהטילו שבטי הוולאכים על ערי צפון יוון.
בנימין הגיע לקונסטנטינופול, בירת האימפריה הביזנטית, בימי שלטונו של מנואל הראשון, והוא מותיר תיאור ססגוני ורב רושם של העיר הגדולה והעשירה שעוררה את התפעלותו (העיר השנייה בגודלה בעולם של אותה תקופה, שנייה בגודלה רק לבגדאד), סדרי השלטון והיחסים בין בני הדתות השונות, ואת השנאה הרבה שרחשו היוונים כלפי היהודים בעיר. מקונסטנטינופול המשיך בנימין לאורך חופי טורקיה והגיע לרודוסטו, גליפולי וקלש. הוא הפליג בים התיכון ועבר באיים מיטלין, חיוס, סאמוס, רודוס וקפריסין, כאשר באיי הים התיכון התגוררו אלפי יהודים והיו בהם קהילות גדולות ומבוססות. מקפריסין הפליג בנימין צפונה, ושב אל חופיה הדרומיים של טורקיה, בסמוך לטרסוס.
חופו המזרחי של הים התיכון וארץ ישראל.
מטרסוס נסע בנימין מטודלה מערבה והגיע לאנטיוכיה שעל שפך נהר האורונטס, שהיהודים הבודדים שבה עסקו באומנות ייצור זכוכית, וממנה הדרים לאורך חופי הים התיכון אל לודקיה וג'בלה. שם הכיר בנימין את בני הפלג האיסמעילי חשישיון, שנלחמו בצלבנים ששלטו בלבנון, ותיאר את מסירותם לחיים ולמוות עבור ראש דתם "שיך אל חשישין", עם החשישיון נפגש בנימין שנית גם כאשר הגיע לפרס.
הוא המשיך לטריפולי, גבל וביירות. מעניינת הבחנתו בין ג'בלה (כיום בסוריה) ובין גבל המקראית (ביבלוס) שמדרום לטריפולי, בעוד שתיהן מכונות בפיו "גיבל". בעוד ג'בלה מזוהה בעיניו עם "בעל גד אשר בבקעת הלבנון" המקראית, הרי שגבל "האחרת" הדרומית מכונה בפיו "גיבל בני עמון", ואת שרידי המקדשים הפגאניים בעיר זיהה כ"שיקוץ בני עמון".
מביירות המשיך בנימין דרומה לאורך החוף והגיע לצידון. מביקורו בצידון הותיר בנימין תיאור סטראוטיפי של הדרוזים שהוא למעשה העדות הראשונה בהיסטוריה של אדם ממוצא אירופאי על העדה: "וקרוב מהם כמו עשרה מילין אומה אחת נלחמים עם אנשי צידון, היא האומה הנקראת דרוזיאין, והם פגנוש ואין להם דת, ויושבים בהרים ובנקיקי הסלעים, ואין מלך או שר שולט עליהם כי בעצמם הם יושבם בין ההרים, ועד הר חרמון גבולם מהלך שלושה ימים. ויש להם חג אחד בשנה ובאים כלם אנשים ונשים לאכול ולשתות ביחד. ואומרים שהנפש בעת יציאתה מגוף אדם טוב תכנס בגוף ילד קטן הנולד באותה שעה ואם אדם רע הוא תכנס נשמתו בגוף הכלב או בגוף הבהמה (גלגול נשמות), וזה דרכם כסל למו. ואין דרים ביניהם יהודים כי אם באים אליהם בעלי אומנות וצובעים ויושבים ביניהם באומנות ובסחורה וחוזרים לבתיהם. והם אוהבים ליהודים, והם קלים ברגליהם לרוץ על ההרים ועל הגבעות ואין אדם יכול להילחם עמהם". מצידון המשיך במסעו דרומה ועבר בסרפנד אותה זיהה כצרפת המקראית, והגיע לצור, וממנה לעכו.
משהגיע לעכו, "תחילת ארץ ישראל", נטש בנימין את מסלולו הקבוע מראשית נסיעתו, הצמוד לחופי הים התיכון, ופנה למסעיו בארץ. ממסעו בארץ הוא הותיר רישום מפורט ומדוקדק, שכולל את זיהוי המקומות התנ"כיים כפי שהבין. מעכו נסע בנימין לחיפה, אותה זיהה בטעות עם היישוב המקראי גת חפר בו נולד יונה הנביא. בחיפה תיאר בנימין את מערת אליהו, ושרידים על ראש ההר בהם ראה את שרידי המזבח שבנה אליהו הנביא. הוא המשיך דרומה ותיאר מקום בשם "כפר נחום" (כנראה באזור עתלית או מזרחית לה) "והוא מעון מקום נבל הכרמלי", ואת קיסריה "היא גת אשר לפלשתים... והיא עיר יפה וטובה מאוד על הים". מקיסריה הדרים בנימין ללוד שנקראה אז סנט ג'ורג', וממנה שב ונסע צפונה אל סבסטיה ותיאר את חורבות העיר שומרון המקראית שבה.
מסבסטיה הגיע בנימין לשכם "ובה כמו אלף כותים השומרים תורת משה עליו השלום לבדה וקורין להן שומרונים...", וממנה אל הר הגלבוע, ובסיום מסעו מהגלבוע דרומה הגיע לירושלים, "היא עיר קטנה ובצורה עם שלוש חומות ובה אנשים הרבה וקורין להם הישמעאלים יעקוביים וארמיים ויוונים וג'ורג'יים ופרנקים ומכל לשונות הגויים". לדבריו גרו בירושלים באותה עת ר' (=200) יהודים, אך לטענת מיכאל ארליך מדובר ככל הנראה בטעות של המעתיק, וצריך לומר ד' (=4), שכן כעשור לאחר מכן ביקר בירושלים הנוסע פתחיה מרגנשבורג והוא מספר על יהודי אחד בלבד שגר בה. הוא הותיר גם תיאור מרתק של אנשי מסדר הטמפלרים, של הרובע היהודי, הר הבית, אורוות שלמה, יד אבשלום, השילוח, והר ציון. הוא מספר אגדה מרתקת על קבר דוד המלך בהר ציון, לפיה 15 שנה לפני ביקורו בירושלים נכנסו פועלי הפטריארך לתוך המערה שתחת קבר דוד המלך וראו את אולמות קברי המלכים, וכי פתח הקבר נסתם והועלם בפקודת הפטריארך.
מירושלים המשיך בנימין לבית לחם ועבר בדרכו בקבר רחל, משם המשיך לחברון וביקר במערת המכפלה. הוא מספר כי המצבות הגדולות המוכרות לנו כיום משמשות לתפילות ה"תועים" (הנוצרים), אך היהודים נכנסים באמצעות שוחד אל תוככי המערה ובה מצבות אחרות של קברי האבות. מחברון המשיך לבית גוברין, וממנה הגיע ללטרון. נראה כי נסע מזרחה מלטרון וביקר בנבי סמואל ובגבע בנימין אותה זיהה בשטח הכפר שועפאט בצפון ירושלים. מסלול נסיעתו משם איננו ברור, אך בתום דרך קצרה הגיע לרמלה אותה זיהו הצלבנים בטעות עם הרמה המקראית, וממנה ליפו.
מיפו נסע בנימין דרומה לכיוון יבנה, אשדוד ואשקלון, שב צפונה ועבר שוב בלוד, עמק יזרעאל והגיע אל הגליל.
בגליל ביקר בנימין בקברי הצדיקים הרבים שבו. הוא ביקר בציפורי בקבר רבי יהודה הנשיא, בטבריה בקבר רבן יוחנן בן זכאי, בגוש חלב ובמירון. במירון בנימין אינו מזכיר את קבר רבי שמעון בן יוחאי אלא את קברי שמאי והלל. הוא ביקר בעלמה וציין את קברי התנאים רבי אלעזר בן עזריה, רבי אלעזר בן ערך, חוני המעגל, רבן שמעון בן גמליאל ורבי יוסי הגלילי. מעלמה המשיך לתל קדש אותו זיהה עם קדש נפתלי, והגיע לבניאס, בה ראה את שרידי המקדשים הפגאניים וחשב אותם לשרידי העיר המקראית דן הסמוכה.
יש חוקרים שטוענים שתיעוד מעברו בארץ ישראל אינו מתיישב עם המסלול ההגיוני שעשו עולי רגל זאת מאחר שישנן קפיצות צפונה ודרומה שאינן מוסברות, כמו המעבר מלוד לסבסטיה שבשומרון, אף על פי שההמשך ההגיוני מלוד הוא לירושלים. לאור זאת, מוצע הסבר שהרישומים לא היו מסודרים בסדר כרונלוגי ונערכו רק אחרי סיום המסע.
סוריה, בבל, תימן.
מארץ ישראל המשיך בנימין מטודלה לסוריה והגיע לדמשק. בעוד ארץ ישראל וכל המקומות בהם עבר קודם היו תחת שלטון נוצרי, סוריה הייתה תחת שלטון נור א-דין הטורקי-מוסלמי. דמשק הייתה לדברי בנימין "עיר גדולה ויפה מאוד ומוקפת חומה, והיא בארץ גנות ופרדסים מהלך ט"ו מילין מכל צד, ולא נראה מדינה העושה פירות כמוה בכל הארץ". בנימין תיאר בהתפעלות את המסגד האומיי הגדול בדמשק שבנה וליד הראשון "ואין כבניין ההוא בכל הארץ". בדמשק פגש בנימין בקהילה יהודית גדולה ותוססת בעלת 3000 משפחות, ואת הישיבה הגדולה שבעיר ותלמידי החכמים הרבים שבה, ואף ציין את קהילות הקראים והשומרונים בעיר.
בנימין המשיך במסעו ועבר בסלכאת שבדרום סוריה, בבעלבק שבלבנון, ואת שרידי המקדשים ההלניסטיים שבה חשב לארמונות שבנה שלמה המלך לבת פרעה, ואף הוסיף כי "אומרים שנעשה בניין זה על ידי אשמדאי". הוא המשיך צפונה ועבר בתדמור (פלמירה) בה הייתה קהילה יהודית גדולה שלדברי בנימין שיתפה פעולה עם הערבים נגד הצלבנים והטורקים, והגיע אל חומס וחמאת שליד נהר האורונטס. גם כאן, כאשר שגה במסעו בלבנון, שב בנימין על שגיאתו, וראה בצפון לבנון את ארץ בני עמון, ואת נהר האורונטס חשב לנחל יבוק, ולבסוף הגיע לחלב, "והיא עיר מלוכה למלך נור-אל-דין ... ובה כמו אלף וחמש מאות יהודים".