ב-27 במאי 1975 יצא האלבום Venus and Mars, הרביעי של להקת Wings, והוא אחד משני האלבומים המצליחים ביותר של הלהקה והגיע למקום הראשון במצעדי הפזמונים של בריטניה, ארה"ב ומדינות רבות אחרות. האלבום האחר מבין שני המצליחים ביותר, הוא קודמו, Band on the Run, שיצא כשנה וחצי קודם. האלבום Venus and Mars הוא גם האלבום עם המספר הגדול ביותר של שירים שביצעה Wings בהופעה חיה. בשנת 1976 יצאה הלהקה לסיבוב ההופעות Wings Over America, ובמהלכה ביצעו, בין היתר, את השירים Venus and Mars, Rockshow, You Gave Me the Answer, Magneto and Titanium Man, Letting Go, Spirits of Ancient Egypt, Medicine Jar, Call Me Back Again ו- Listen to What the Man Said. מדובר בתשעה שירים מתוך שניים-עשר השירים שבאלבום וזהו שיא לעומת כל אלבום אחר.
יש באלבום שיר אחד שפול מעולם לא ביצע על הבמה והוא הבלדה הנוסטלגית Love in Songשהוא פנינה אמיתי, אם כי שיר פחות ידוע. פול מנגן בשיר הזה את הקונטרבס של ביל בלאק, מי שהיה חבר בהרכב שליווה את אלביס פרסלי. פול קיבל את הכלי הזה ליום הולדתו ה-32 מלינדה, בת זוגו והציג אותו בהופעה הטלוויזיונית Chaos and Creations in Abbey Road בשנת 2005.
הנה השיר Love in Song:
הנה פול בהופעה הטלוויזיונית Chaos and Creations in Abbey Road מבצע את השיר Heartbreak Hotel בעזרת הקונטרבס של ביל בלאק:
עם זאת, האלבום Venus and Mars ייזכר תמיד כאלבום שפספס את ההזדמנות להיות האלבום שבו חזרו לעבוד ביחד ג'ון לנון ופול מקרטני. אחרי שבמרץ 1974 נפגשו השניים לראשונה מאז פירוק הביטלס, באולפן הקלטות והקליטו ג'אם עם מספר מוזיקאים, כולל סטיבי וונדר, הם המשיכו לשמור על קשר. פול הזמין את ג'ון להצטרף אליו לאולפן ההקלטות כדי לקחת חלק באלבום Venus and Mars. ג'ון סיפר לבת זוגו אז, מאי פאנג, שהוא ישמח לעשות זאת ואף שקל לכתוב שיר חדש ביחד עם פול. כל כך רצה ג'ון לחזור לעבוד עם שותפו לשעבר שאפילו התכחש לשיר How Do You Sleep? ואמר שהוא לא התכוון לפול אלא לעצמו. הביקור המתוכנן של לנון בסופו של דבר לא התממש שכן בינתיים חזר לניו יורק והאלבום Venus and Mars לא הפך לאלבום האיחוד של הצמד לנון-מקרטני וזה הפספוס הגדול שלו.