אחרי שהחליטו הביטלס להפסיק להופיע, באמצע שנת 1966, הם לקחו פסק זמן שכל כך היו זקוקים לו וג'ון נסע לגרמניה ולספרד כדי להשתתף בצילומי הסרט How I Won the War וג'ורג' להודו כדי ללמוד סיטאר ובעיקר לספוג את תרבות המזרח. אז החליט פול שהוא רוצה לנסוע רחוק לאן שהוא אבל מאחר ולא רצה שיזהו בתור פול מהביטלס היה עליו לשנות את החזות החיצונית שלו. גם לו, למרות שמאד רצה להמשיך להופיע, נמאס מהשיגעון והתהילה המטורפים שהביאו הביטלמניה. אז אימץ פול מראה שונה ולבש דמות חדשה, וכאן, ממש כאן, ניבט הזרע שמאוחר יותר הוביל לקונספט שמאחורי האלבום Sgt. Pepper's Lonely Hearts Club Band, כלומר להתחפש ללהקה אחרת.
כבר בתקופת הביטלמניה לבש פול פעמים רבות תחפושות שאפשרו לו לצאת ולשוטט ברחובות בלי שאנשים יזהו אותו, וזה תמיד יצר אצלו תחושה מאד משחררת. אפילו פעם, כשרצה לבדוק עד כמה התחפושת שלו מכסה על זהותו האמיתית, ניגש לחדר של ג'ורג' שהיה משוכנע שמולו אדם זר לחלוטין שמעולם לא פגש. ג'ורג' אמר אז בכעס "מי אתה? מה התה רוצה? מי נתן לך להגיע לכאן?" ואז חייך פול ואמר לו "זה אני, ג'ורג'" וג'ורג' פשוט ענה לו "הו, שיט!"
פול החליט לנסוע לצרפת ואחרי שסיים את מחויבותו לקחת חלק, יחד עם רינגו, בטקס חלוקת פרסים של המגזין Melody Maker שהתקיים ב-14 בספטמבר 1966, הכין את התחפושת שלו לקראת הנסיעה. דבר ראשון ביקש מחברת Wig Creations, שהייתה אחראית על האיפור במהלך צילומי הסרט A Hard Day's Night, להכין לו שפם מלאכותי. בנוסף, שינה פול את התסרוקת שלו והרכיב משקפיים מזויפות. על כך הוא סיפר:
הם מדדו אותי והתאימו לי שפם מלאכותי עם דבק לפי צבע השיער שלי כך שזה ייראה כמו שפם אמיתי. הרכבתי גם משקפיים עם עדשות שקופות שהיו לי, וכל זה גרם לי להראות שונה. לבשתי גם מעיל כחול ארוך וסירקתי את השיער שלי עם ג'לי כך שאיש לא יזהה אותי. זה היה טוב ודי משחרר עבורי
ב-6 בנובמבר טס פול לפריז ובילה שם שבוע לבדו כשהוא לא מוריד ממנו את התחפושת למעט לילה אחד שבו לא הורשה להיכנס למועדון לילה עד שנאלץ לגלות שהוא פול מהביטלס. לאחר מכן, נסע פול לבורדו, שם נפגש עם מל אוונס, העוזר הנאמן ועל כך סיפר פול:
הביקור בפריז היה שחזור של הביקור שערכתי שם עם ג'ון לרגל יום הולדתו ה-21. ישבתי בחדר במלון שלנתי בו וכתבתי יומן. הסתובבתי בעיר, צילמתי ובלילה ירדתי לאכול ארוחת ערב. ישבתי לבד ליד השולחן וזה היה מושלם להיות בחופשה בלי שאף אחד זיהה אותי וגם לטעום שוב את טעם האנונימיות. ישבתי לבד וחשבתי על כל מיני רעיונות אמנותיים. אם רציתי יכולתי לכתוב רומן בקלות.
אחרי שהחופשה של כשבועיים בצרפת, נסעו פול ומל אוונס ב-12 בנובמבר לספרד. הם עצרו בעיר החוף סן סבסטיאן, ואז נסעו למדריד, אחר כך לקורדובה ואז למלגה כאשר הרעיון היה להגיע בסוף לאלמריה כדי לבקר את ג'ון באתר הצילומים של הסרט How I Won the War. עם זאת, התכניות של פול השתבשו כשהתבשר כי הצילומים הסתיימו וג'ון כבר חזר לאנגליה. מאוכזב והמשועמם מהנהיגה הארוכה ברכב האסטון מרטין שלו, חיפש פול משהו אקזוטי לעשות ואז החליט לנסוע לספארי בקניה.
אחרי שדאג שהרכב שלו יוחזר ללונדון, עלו פול ואוונס לטיסה לניירובי, שם הצטרפה אליהם בת הזוג של פול, השחקנית ג'יין אשר. השלושה בילו בפארק הלאומי צאבו ושכרו מדריך מקומי בשם מוזס שלקח אותם לאתרי התיירות המקומיים.
הביקור בטבע הפראי של קניה קניה נתן לפול את ההשראה לכתוב את השיר Wild Life שיצא באלבום הבכורה של להקת Wings שיצא בשנת 1971 ונשא את אותו שם. על כך סיפר פול:
השירWild Life קשור לספארי שעשיתי, שם ראיתי שלט שממנו לקחתי את השורה שבשיר The animals have the right of way (לבעלי החיים זכות קדימה). זה מאד הרשים אותי, אתה פתאום מבין את הכבוד והכוח שיש שם לחיות הבר שנותנים להן זכות קידמה. זאת, בעוד שכולנו, בני האדם, כל כך מלאים בחשיבות עצמית. אז כתבתי את השיר הזה כי אנחנו "המין העליון" ולמרות זאת אנחנו אלה שהורסים את הטבע וזה כל כך לא צודק
פול, ג'יין ומל בילו את הלילה האחרון ב-YMCA בניירובי ועלו לטיסה בחזרה לאנגליה ב-19 בנובמבר. לרוע המזל, יומן המסע שכתב פול, כמו גם סרט המסע שצילם, אבדו וחלק מהסלילים נגנבו ע"י מעריצות שפרצו לביתו בלונדון. זו הסיבה שמעט מאד תמונות שרדו אז הנה קטע קצר מהחומר שצילם פול: