האלבום Band on the Run היה עבור המבקרים חזרתו של פול מקרטני השותף המוכשר של ג'ון לנון, זה שהיה איתו כוח מוביל בלהקת הביטלס. לפני האלבום הזה, לא זכו עבודותיו הקודמות להתלהבות גדולה במיוחד מצדם. פול לא היה מרוצה מההתייחסות הזו, שכן סבר שעבודותיו הקודמות זכו להערכת חסר מהם, ולכך התכוון כשאמר ש"המבקרים רואים הכל בשחור-לבן", והוסיף:
החזרה האמיתית של פול מקרטני מהביטלס הייתה כבר בשיר Maybe I’m Amazed
האלבום Band on the Run הוא אחד האלבומים הטובים ביותר, אם לא הטוב שבהם, של פול בתקופת להקת ווינגס ובכלל, ונראה כאילו הוא עונה על הקלישאה שאומרת שאמנות צומחת מתוך מצוקתו של האמן, שהרי תהליך יצירתו והפקתו היה רצוף משברים עבור פול:
· להקת ווינגס כמעט התפרקה רגע לפני תחילת ההקלטות על האלבום, כאשר הגיטריסט הנרי מקולו והמתופף דני סיוול התפטרו. לפול לא היה זמן לחפש להם מחליפים, וההקלטות, שהתחילו באוגוסט 1973, נעשו בהרכב חסר, והשתתפו בהן חוץ מפול, רק הגיטריסט דני ליין ובת זוגו, לינדה. הדבר חייב את פול לא רק לשיר ולנגן בגיטרת הבס ובקלידים, אלא גם לתפוס את מקום הגיטריסט והמתופף.
· פול רצה להקליט את האלבום Band on the Run במקום אקזוטי, מחוץ לבריטניה, בתקווה לקבל ממנו השראה. ג'ינג'ר בייקר, המתופף לשעבר של להקת Cream וחובב המקצבים האפריקניים, הציע לו את האולפנים שהקים בעיר איקג'ה, שבניגריה, ARC Studios. מאחר והאולפנים של בייקר היו מתחת לסטנדרט הנדרש, הורה פול להעביר את הציוד החסר מלונדון לאולפנים של בייקר. אולם, חברת EMI, שפול היה חתום איתה על חוזה הקלטות, דרשה שההקלטות ייעשו באולפנים שלה בלאגוס, בירת ניגריה. זה חייב את פול להסיע שוב את הציוד מאולפני ARC Studios לאולפני EMI שבלאגוס, שהתברר שגם הם היו מתחת לכל סטנדרט. הדבר מאד הרגיז את בייקר וכפיצוי הקליט פול באולפנים שלו את השיר Picasso's Last Words, כשבייקר מלווה אותו על התופים.
· באחד הערבים, בעודם הולכים ברגל בחזרה לבית המלון, הותקפו פול ולינדה ע"י חבורת שודדים מקומיים, שגנבו מהם את ההקלטות עם טייקים של השירים שהספיקו להקליט, כמו גם כסף ורכוש אישי. לינדה צעקה עליהם נואשות לא לפגוע ב"ביטל פול", אבל לא נראה שהם ידעו מי הוא פול מקרטני ומי הם היו הביטלס.
· במהלך ההקלטות התעורר עימות בין פול לפלה קוטי, מוזיקאי ואקטיביסט פוליטי ניגרי, שהאשים אותו בכך שהוא מנצל את היבשת השחורה וגונב את המוזיקה האפריקאית. כך, הסית קוטי את המוזיקאים המקומיים שהשתתפו בתחילה, בהקלטות של האלבום של פול.
האלבום Band on the Run יצא ב-7 בדצמבר 1973, והגיע למקום הראשון במצעדי הפזמונים בבריטניה ובארה"ב. עבור פול, הצלחתו של האלבום, גם בקרב הקהל וגם בקרב המבקרים, הייתה ההכרה שכל כך היה זקוק לה מאז שהתפרקה להקת הביטלס. פול גם זכה להכרה ולא פחות חשובה, והיא באה דווקא מקית 'מון, המתופף המצוין של להקת The Who, ששיבח אותו על ביצועיו על התופים. אבל את ההכרה החשובה מכולן, קיבל פול מג'ון לנון, שאמר לתקשורת שהוא "אוהב את האלבום החדש של פול".
הנה השיר Band on the Run מתוך סיבוב ההופעות Wings Over the World Tour בשנת 1976:
