Новый альбом Wings стала записывать в январе 1976 года. Поскольку критики заявляли, что музыканты группы всего лишь аккомпанируют Полу, Маккартни предложил участникам Wings исполнить ведущий вокал в некоторых песнях, и, заодно, написать свои песни для альбома. Так, на пластинке Wings At The Speed Of Sound появились песни Wino Junko Джимми Макалоха и Time To Hide Денни Лейна. А композицию Must Do Something About It спел барабанщик Джо Инглиш. Вообще, Пол, с одной стороны, планировал создать группу, в которой все участники были на равных правах, а с другой понимал, что только его имя даёт Wings необходимую рекламу.

Альбом Wings At The Speed Of Sound вышел 25 марта 1976 года. Его отметили как критики, так и слушатели. В США он продержался на первом месте хит-парада семь недель, не дав подняться на высшую ступень сборнику The Beatles Rock `N` Roll Music. Теперь можно было отправляться на гастроли по Америке. Помимо нового материала, который благодарно принимала публика, Маккартни мог вставлять в концертную программу хиты The Beatles, в том числе и те, которые раньше никогда не исполнялись на концертах. Репетируя программу, Пол знал, что после окончания гастролей будет выпущен концертный альбом. Он получит название Wings Over America, будет состоять из трёх пластинок, и появится в продаже 10 декабря 1976 года. В 1977 году альбом поднимется на первое место в хит-парадах США.

Это не будет запись одного конкретного концерта. Песни подобраны так, чтобы одновременно отразить игру Пола на разных инструментах, показать песни, автором которых Пол не был, и, наконец, напомнить публике о временах The Beatles. Выход альбома дал понять слушателям, что, пожалуй, именно Пол был творческим стержнем распавшейся группы. Джон Леннон как раз ушёл в тень, а гастроли Джорджа Харрисона по США успехом не увенчались. От Ринго Старра никто и не ожидал ничего подобного. 1976 год сложился для Маккартни удачно. Журнал Rolling Stone назвал Пола лучшим исполнителем года, а газета Daily Mirror поставила группу Wings на первое место среди рок-групп.

Но самый коммерческий успех Wings пришёлся на конец 1977 года. Группа выпустила сингл Mull Of Kintyre. Он продержался на первом месте хит-парада девять недель, и при этом его продали тиражом свыше двух миллионов экземпляров. Рекламу песне сделал и красивый видеоряд, который не мог оставить равнодушным ценителей живой природы. Неповторимый звук создал специально приглашённый для этой цели оркестр волынщиков.

Новый альбом Wings в 1977 году не выпускала. Во-первых, в группе произошла смена состава. Во-вторых, надо было отдохнуть после длинного мирового турне. В-третьих, 1977 год вошёл в историю музыки, как год панка, и на его фоне баллады смотрелись инородным телом. Ну, и в-четвёртых, Линда Маккартни была беременна. 12 сентября 1977 года у четы Маккартни родился сын Джеймс.

Как и в случае с альбомом Venus And Mars новая пластинка получила название по первой песне London Town. В общей сложности запись длилась почти год, с февраля 1977 года по январь 1978. Начали записывать песни на яхте, оборудованной под студию, отсюда и первоначальное название альбома Water Wings. Из 13 песен в окончательную версию альбома вошли только семь. В мае группа вернулась в Британию, поскольку Линда не могла больше находиться на яхте. Тогда-то группу покинули два её участника, и с семьёй Маккартни остался только Денни Лейн. Но опыт записи втроём уже был, так что в таком усечённом составе Wings довели альбом до конца. На обложку альбома попала только эта троица.  

В продажу London Town поступил 31 марта 1978 года. Продавался он хорошо, более миллиона копий разошлось по миру, но вот достигнуть первого места в хит-парадах по обе стороны Атлантики ему было не суждено. До него добрался только сингл с песней With A Little Luck. Ещё одна песня, Girlfriend, была написана специально для Майкла Джексона, и не должна была присутствовать на пластинке. Но Пол поменял решение и включил её в альбом. Джексон выпустил её на своём альбоме годом позже.

2 ноября 1978 года на прилавках магазинов Британии появился сборный альбом Wings Greatest. Большинство изданных на нём песен выходили ранее на синглах. Рекламная акция в поддержку альбома была снята телевизионной компанией.  Артисты, снятые в ролике, распевали песни с альбома в различных общественных местах Лондона. В самом конце, возле известного пешеходного перехода с обложки альбома The Beatles Abbey Road появлялись Пол и Линда Маккартни вместе с Денни Лейном. Тонкий английский юмор способствовал продаже пластинки.   

В дальнейшие планы Пола входили запись нового альбома, очередное мировое турне, написать саундтрек к мультфильму Rupert The Bear, и снять художественный фильм с участием Wings. Для этих целей он пригласил продюсера Криса Томаса и сценариста Вилли Рассела. А также позвал в группу недостающих ему музыкантов.

Крис Томас работал ранее с группой Sex Pistols, так что влияние панка и новой волны не могли не сказаться на звучании альбома. Пол согласился с идеями Криса, желая идти в ногу с модными музыкальными течениями. И в тоже время Пол стремился вернуться к близкому ему рок-н-роллу. Отсюда и название нового альбома Back To The Egg. Все песни, кроме одной, написал Маккартни. Работать над песнями Wings начали 29 июня 1978 года на домашней студии Пола в Шотландии, а закончили только в феврале 1979, в Лондоне, сменив попутно четыре студии звукозаписи.

Материала получилось больше, чем на одну пластинку. Пол задумал выпустить концептуальный альбом, и тщательно подходил к подборке песен. Для рекламы пластинки была выбрана песня Goodnight Tonight. Написанная в стиле диско, она никак не вписывалась в концепцию всего альбома, но вызывала симпатию слушателей. Вышедший 23 марта 1979 года сингл хоть и не добрался до первого места в хит-парадах, но продавался успешно, было продано более миллиона копий.

Альбом Back To The Egg повторить успех сингла не смог. Это касается и продажи, и реакции критиков. Журнал Rolling Stones просто уничтожил альбом. После такого приёма Пол Маккартни решил на время побыть в одиночестве. Гастроли Wings были запланированы на осень 1979 года, а летом Пол у себя дома готовил материал для нового альбома, который он решил записать сам, как это было десять лет назад. Тот альбом назывался скромно – McCartney. Так что название для следующего альбома, записанного Полом самостоятельно, напрашивалось самим собой - McCartney II.

Работа в домашней студии продолжалась два месяца, в июле и августе 1979 года. Пол продолжил движение в сторону от своего привычного музыкального стиля. На этот раз он широко использовал синтезаторы, добавив к ним студийные эффекты, чего не применял при записи первого альбома. В общей сложности Пол сочинил и сделал черновые записи порядка 20 песен. Однако сразу довести альбом до ума не получилось. В планах Wings стояло мировое турне, и Пол с группой стал репетировать гастрольную программу. Выпуск альбома был отложен до окончания гастролей.

В ноябре и декабре Wings давали концерты в Британии. На январь была запланирована поездка в Японию. Последний раз Пол был там в 1966 году с The Beatles. Позже въезд в Японию Маккартни запретили местные власти из-за того, что Пол покуривал марихуану. Теперь запрет был снят, и Wings 16 января 1980 года прибыли в Токио. Но во время таможенного досмотра в багаже Пола вновь была обнаружена марихуана, после чего последовал арест. Гастроли были сорваны. Пол Маккартни отсидел в токийской тюрьме 9 дней, после чего был отправлен домой. Мировое турне Wings на этом закончилось. Пол вернулся на свою ферму и продолжил работу над сольным альбомом. О дальнейшей судьбе группы решения пока не было принято. Неустойка от сорванных гастролей составила 1 800 000 фунтов, Полу было над чем подумать.

16 мая 1980 года McCartney II появился на прилавках магазинов Британии, 22 мая в США. Реакция критиков и слушателей была неоднозначной. Такого звучания песен Пола ещё не приходилось слышать, а также на пластинке нашлось место чисто инструментальным композициям. Всего на пластике их было 11. Заглавная песня Coming Up очень понравилась Джону Леннону, и отчасти побудила его вернуться к творческой деятельности. Сам же альбом McCartney II занял первое место в Британии и третье место в хит-параде США. В целом, пластинка публике понравилась.

В конце 1980 года Пол Маккартни планировал издать сборный альбом Hot Hits, Cold Cuts. На нём были представлены неизданные песни, которые Wings записали с 1972 по 1979 года. Однако издан этот сборник будет издан намного позже. А вот саундтрек к мультфильму Rupert The Bear Пол запишет и издаст вовремя.

Убийство Джона Леннона заставило Пола Маккартни пересмотреть свои планы на будущее. Выступать с концертами в ближайшее время Полу совершенно не хотелось. Любой идиот теоретически мог выстрелить в него. Спасала от тяжёлых мыслей только студийная работа. Осенью 1980 года отношения Пола и Джона значительно улучшились по сравнению с 1970 годом. Только Йоко Оно не одобряла их. Обманывала Пола, говоря, что Джона нет дома, и не передавала тому телефонную трубку. У меня нет никаких сомнений, что ещё до конца ХХ века The Beatles снова собрались бы вместе, если бы не смерть Джона. Но история не знает сослагательно наклонения. В апреле 1981 года Пол Маккартни получил несколько писем с угрозами в свой адрес. После чего было Полом было принято окончательно решение о расформировании Wings. 27 апреля 1981 года Пол сообщил об этом публично.