Ещё в 1954 году, направляясь в автобусе в школу, Пол случайно познакомился с Джорджем Харрисоном, жившим неподалёку, с которым вскоре сдружился. Теперь он уговорил Джона принять юного приятеля в Quarrymen, тем более, что сам скептически относился к музыкальным способностям Стюарта Сатклиффа, школьного друга Леннона. К 1960 году, перебрав несколько названий, группа под названием The Silver Beatles направилась в Гамбург, где сократила название до The Beatles.

The Beatles

Джим Маккартни не хотел отпускать сына, но вынужден был согласиться, когда Пол заявил, что будет зарабатывать до 10 шиллингов в день: аргумент оказался весомым для отца, после войны испытывавшего хронические денежные трудности. В Гамбурге, где The Beatles оказались под опекой антрепренёра Бруно Кошмидера (в прошлом — циркового клоуна), Пол вырос из самодеятельного музыканта в профессионала; считается, что именно 800 часов, проведённые на сцене трёх клубов этого города, и превратили The Beatles в группу мирового уровня. Первым принял The Beatles в качестве резидентов Indra. Условия проживания были ужасными: музыкантов разместили в заброшенном кинотеатре, мыться им приходилось в туалетах. Но выступления по семь дней в неделю в жёстком графике (с 20:30 до двух ночи с тремя получасовыми перерывами) стали для группы незаменимой школой сценического мастерства. Кроме того, — «Мы постоянно старались привлечь в клуб прохожих; это был своего рода учебный опыт: как завлечь тех, кто видеть тебя не желает», — вспоминал Маккартни. Затем группа перешла в Kaiserkeller: здесь график работы был более щадящим (час игры — час отдыха, посменно с Rory Storm and the Hurricanes), но музыканты оказались в самом пекле вражды между местными «экзис» (от existentionalists) и «рокерами». Впрочем, неизменно защищал «битлов» легендарный вышибала (и гангстер) Хёрст Фашер с приятелями: «Самым поразительным было для нас, когда мы узнали этих людей (а узнали мы их очень хорошо), то, что они, оказывается полюбили нас — ну просто как братьев». По словам Пола, опекавшие их бандиты едва ли не плакали, когда пришла пора расставаться.

Работа на Кошмидера завершилась вскоре после того, как The Beatles перешли в новый, конкурирующий клуб Top Ten. Произошло это в значительной мере благодаря Маккартни, который во время прослушивания произвёл на владельцев неизгладимое впечатление своими имитациями под Литтл Ричарда. В конечном итоге и обратно в Ливерпуль The Beatles отправились благодаря Полу, с Питом Бестом, устроившим пожар в комнате, откуда съезжал. Бруно Кошмидер вызвал полицию, Пол и Пит провели три часа в участке, после чего были депортированы.

В декабре 1960 года Beatles начали выступать в Ливерпуле, в частности, 27 декабря дав в Litherland Town Hall концерт, который считается поворотным в их карьере. Пол Маккартни здесь ошеломил зрителей своим исполнением «Long Tall Sally» и практически спровоцировал в зале (как писал Б. Майлз) первый всплеск битломании. 21 марта 1961 года Пол Маккартни вместе с The Beatles отыграл свой первый концерт в ливерпульском клубе «Каверн». Поняв, что конкуренты по клубной сцене играют те же каверы, что и они с Джоном, он убедил последнего заняться работой над оригинальным материалом. В апреле 1961 года группа вернулась в Гамбург и здесь сделала свою первую запись: «My Bonnie» с Тони Шериданом.

До 1961 года Пол, как и Джон, играл на ритм-гитаре, а бас-гитару брал в руки лишь в тех случаях, когда Стюарт Сатклифф не мог выйти на сцену. Постоянным бас-гитаристом Маккартни стал только летом 1961 года, когда по истечении гамбургского контракта Сатклифф покинул группу. Поводом тому явился конфликт во время концерта в Гамбурге, когда (согласно биографии Боба Спитца и по словам Дот Рон) «…Стю снял бас-гитару, положил её на пол, набросился на Пола и они отколошматили друг друга прямо на сцене». «Существует теория о том, что я будто бы выпихнул Стю из группы, чтобы завладеть его бас-гитарой. Забудьте! Никто не мечтает играть на басу — во всяком случае, не мечтал в те годы. Бас-гитара — это то, с чем стоят толстые мальчики в глубине сцены…», — вспоминал Пол. Как бы то ни было, он с этих пор и стал бас-гитаристом, получив в своё пользование инструмент Hofner 500/5, на котором играл Сатклифф. Позже, в 1962 году, он приобрёл Hofner 500/1, который стоил недорого и его (из-за симметричной «скрипичной» формы) было легко переделать под игру левой рукой.