Свой новый альбом Пол Маккартни стал записывать в ноябре 1974 года, в Лондоне, но весь основной материал был записан в феврале 1975, в Новом Орлеане. Назван он был по заглавной песне Venus And Mars, но первой песней, изданной на сингле, будет другая – Listen To What The Man Said. И альбом, и сингл займут первые места хит-парадов Британии и США. Джон Леннон хотел приехать к Полу на запись альбома, и, что было вполне вероятно, даже поучаствовать в ней. Но к Джону вернулась Йоко, и этим планам не суждено было сбыться.
После выхода альбома Venus And Mars 27 мая 1975 группа Wings отправилась в мировое турне, которое началось в сентябре, в Британии. Но ещё более важное событие ожидало Пола Маккартни в конце 1975 года. Наконец-то суд принял решение в его пользу, и теперь Пол мог публично исполнять свои песни, написанные им во времена The Beatles.