באולם של כנסיית סנט פיטר, בשוכנת וולטון שבליברפול, נפגשו לראשונה ג'ון לנון ופול מקרטני, ב-6 ביולי 1957, זמן קצר לפני שעת השקיעה. פול שמאד התרשם מג'ון, ובעיקר מעמידתו על הבמה ומיכולתו לאלתר תוך כדי ההופעה שנתן קודם לכן באותו יום, מאד רצה להרשים אותו בחזרה. ומה שפול עשה מאד הרשים את ג'ון, עד כדי כך שפער הגילאים ביניהם, שנה וארבעה חודשים, כבר לא היה חשוב יותר. בעיקר התרשם ג'ון מנגינת הגיטרה שלו, מהידע לכוון אותה, מהיכולת לזכור בעל פה את כל מילות השירים ואף מהכישרון לחקות באפן מושלם, את קולו הצווחני של ליטל ריצ'ארד, מושא הערצתו. ואז ניצב ג'ון בפני שאלה גורלית: האם להזמין את פול להצטרף ללהקתו, הקווארימן? מצד אחד, הוא ידע שפול יתרום תרומה משמעותית להתפתחות הלהקה, אפילו יותר ממנו; מהצד האחר, חשש ג'ון שבזכות יכולתו המוזיקלית הגבוהה יותר, יאפיל פול על מנהיגותו. הרי עד עכשיו, מעולם לא הטילו חברי הקווארימן ספק כי ג'ון הוא הוא הבוס בלהקה. כעבור ימים מספר, הכריע ג'ון הכרעה לא מובנת מאליה, והזמין את פול להצטרף לקווארימן.
מהרגע הראשון קיבל פול את מנהיגותו של ג'ון, אבל הוא לא התכוון, ולו לרגע, להיות סתם עוד חבר בלהקה. תוך זמן קצר, הורגשה השפעתו החשובה וראוי לציין שתי דוגמאות לכך, אחת בולטת ואחת גורלית:
כדי להמחיש את הדוגמה הראשונה, הבולטת, נבחן את התמונה הראשונה שבה צולם פול כחבר להקת הקווארימן. התמונה צולמה במהלך הופעה של הלהקה, שהתקיימה ב-27 בנובמבר 1957, כארבעה חודשים בלבד מאז שפול הצטרף אליה, באולם ניו קלאבמור הול. בתמונה נראים כל חברי הקווארימן, בפעם הראשונה, בתלבושת אחידה, לבושים חולצות לבנות ועונבים עניבות תואמות. ויותר מזה, בשונה מהם, עומדים ג'ון ופול, זה לצד זה בחזית הבמה, ולובשים גם ז'קטים לבנים. אז דבר ראשון, זה היה פול מי ששכנע את ג'ון לאמץ את הלבוש החדש ולעמוד על הבמה לצדו (ואם מישהו חשב שבריאן אפשטיין היה הראשון שהלביש את הביטלס בחליפות הוא טועה, פול עשה זאת לפניו) ודבר נוסף, הלבוש של שניהם, השונה משל אחרים, ועמידתם בחזית הבמה משדרת כי שניהם שווים זה לזה אך מורמים לעומת האחרים.
הדוגמה הנוספת, הגורלית, היא הצטרפותו של ג'ורג' הריסון ללהקת הקווארימן. בזכותו עבודת השכנוע העיקשת מצדו של פול, כשבעה חודשים בלבד מאז שהצטרף, הצליח לגבור על רתיעתו של ג'ון מפני גילו הצעיר של ג'ורג', ולסדר לו אודישן בקומה השנייה של האוטובוס הירוק שבקו 46.
כשהביטלס הוציאו את האלבום הראשון שלהם, Please Please Me, במרץ 1963, כל השירים שג'ון ופול כתבו ביחד הופיעו תחת הקרדיט "מקרטני-לנון". אומנם אין תיעוד של השיח שהתקיים בין השניים בעניין הזה, אבל היפוך סדר השמות בקרדיטים, הפעם כ"לנון-מקרטני", כבר באלבום השני, With The Beatles, יותר ממרמז על כך שג'ון התעשת די מהר והחליט להבהיר לעולם, ובמיוחד לפול, מי באמת הבוס בלהקה.
בסוף אוגוסט 1966, הופיעו הביטלס בפעם האחרונה בקנדלסטיק פארק שבסן פרנסיסקו. ג'ון וג'ורג' היו המנוע מאחורי ההחלטה לא להופיע יותר, בעוד שפול, למרות שנתן את ברכתו, המשיך להאמין שהופעות מול קהל חיוניות בקריירה של כל להקה. נקודת המפנה הזו, הייתה זרז עבור פול, שיזם והוביל את הפרויקט הבא שלהם, Sgt. Pepper's Lonely Hearts Club Band. אבן הדרך הבאה היו מותו של בריאן אפשטיין, באוגוסט 1967, וההחלטה של כל חברי הביטלס לא למנות מנהל במקומו. בוואקום הזה נכנס פול ביתר שאת, והגה את הפרויקט הבא, סרט ללא תסריט בשם Magical Mystery Tour.
כל אלה לא היו צעדים חתרניים מצדו של פול כנגד מנהיגותו של ג'ון, אלא שג'ון איפשר לו ושיתף איתו פעולה, גם אם לפעמים בחריקת שיניים. וככל שג'ון החל בחיפושיו אחר אפשרויות חדשות לנתב אליהן את דרכו האמנותית, בלי ממש לכלול בהן את חברי הביטלס, הובלתו של פול הלכה ותפסה נפח. כך, אחרי החוויה הכואבת של הקלטות האלבום הלבן, במחצית השנייה של שנת 1968, לקח פול שוב את המושכות ולחץ על חבריו להיכנס אל פרויקט חדש, Get Back. ולאחר שגם הפרויקט הזה התברר כחוויה כואבת, דחף פול את חבריו אל תוך פרויקט אחר, הקלטת אלבום נוסף, אחרון, Abbey Road, ובלבד שכולם יתחייבו לייצר, במהלך ההקלטות, חוויה מרפאה.
המאמצים של פול להטביע את חותמו בלהקה לא היו מוגבלים רק לתחומי המוזיקה והאמנות. גם בתחומים האדמיניסטרטיבי והפיננסי הוביל פול מהלך משלו, שאף יצר קרב אימתני בתוך הלהקה. פול רצה למנות את לי וג'ון איסטמן למנהלים העסקיים של הביטלס, בעוד שג'ון רצה, בתמיכתם של ג'ורג' ורינגו, למנות את אלן קליין לתפקיד הזה. הקרב הזה הפך לעוד יותר מכוער כאשר הקדים פול את ג'ון, באפריל 1970, והודיע קבל עם ועדה על פירוק הביטלס, ואחר כך תבע את חבריו בבית המשפט, במטרה לבטל את החוזה העסקי שקשר ביניהם.
כבר מההתחלה הבינו ג'ון ופול שנרקמה ביניהם תלות הדדית שמצד אחד מפרה אותם ודוחפת אותם להישגים אמנותיים שטרם נראו כמוהם, ומצד שני מייצרת מנהיגות משותפת מאד מאתגרת עבור כל אחד מהם. זה היה קשר סימביוזי שמשום שעמד בבסיס הצלחתם בתור להקת הביטלס, עבורם, אי אפשר היה בלעדיו, אבל באותה עת קשה מאד היה איתו.
