ב-1954 מקרטני פגש לראשונה את ג'ורג' האריסון, לימים חברו ללהקת הביטלס, באחת הנסיעות מטעם בית הספר בו למדו. השניים הפכו מיד לחברים, ומצאו עניין משותף במוזיקה ובנגינה. שנים ספורות לאחר מכן, נפגשו לראשונה מקרטני וג'ון לנון, לאחר שחבר משותף עורך ביניהם היכרות, בסיומה של הופעה של להקתו של לנון ב-6 ביולי 1957. לנון היה ממקימי להקת סקיפל (skiffle) בשם "החוצבים" (The Quarry Men), ולאחר פגישה נוספת הסכים לצרף את מקרטני ללהקה כנגן גיטרה מלווה תוך שהוא מתרשם מיכולות הנגינה שלו. מקרטני ניסה לצרף את חברו, ג'ורג' האריסון, לאותה להקה, והאריסון אכן התקבל ב-1958 בתפקיד של נגן גיטרה מובילה.
1960-1970: שנות הביטלס.
לאחר מספר גלגולים זכתה להקת "החוצבים" לשם הביטלס. למרות הסתייגותה של דודתו של לנון, מימי, ממקרטני בן מעמד הפועלים (לנון היה בן המעמד-הבינוני האמיד), ועוד יותר מהאריסון, בעל המבטא הליברפולי העיקש, הפכו מקרטני ולנון ידידים והחלו כמעט מיד לכתוב שירים ביחד.
הביטלס היו מסגרת מאגדת רופפת ללהקת נערים, ללא מתופף ראוי לשמו ובהרכבים ובשמות שהשתנו תדירות. פריצת הדרך המקצועית הגיע כאשר ארגן אמרגנה הראשון של הלהקה סדרת הופעות במועדון לילה קטן ברובע סט. פאולי בהמבורג שבגרמניה. לקראת סדרת ההופעות צורף ללהקה ידידו של לנון, סטיוארט סאטקליף, כנגן בס וברגע האחרון צורף המתופף פיט בסט. סדרת ההופעות, כמו גם מסעות ההופעות הנוספים בהמבורג, תרמו רבות לגיבושה של הלהקה. אחרי מסע ההופעות הראשון, שהסתיים בגירושם של חברי הלהקה מהמבורג, התפרקה הלהקה למעשה, אך שבה והתאחדה כעבור מספר חודשים, כשמקרטני מלוהק הפעם לתפקיד נגן גיטרת הבס, במקום סאטקליף שנשאר ללמוד בהמבורג.
בסוף שנת 1961 הפך בריאן אפסטיין (אפשטיין) למנהל הלהקה, שינה את הופעתה, ואף הצליח להשיג לה חוזה הקלטות לאחר מספר ניסיונות כושלים. שני השירים הראשונים שהקליטה הלהקה, Love Me Do ו-P.S. I Love You, היו שירים שהכותב העיקרי שלהם היה מקרטני.
במהלך שנת 1963 נהנתה הביטלס מהצלחה כבירה בבריטניה, שבשנת 1964 תורגמה להצלחה גדולה לא פחות בארצות הברית ואחר-כך בעולם כולו. לבד מגרסאות כיסוי לשירים של כותבים אחרים, ושיר אחד של ג'ורג' האריסון, נכתבו כל השירים בשנים אלו על ידי מקרטני ולנון. חלק מלהיטי הלהקה נכתבו על ידי השניים כשהם יושבים "עין מול עין" עם הגיטרות בידם. שירים אחרים נכתבו בעיקרם או במלואם על ידי לנון או מקרטני, אך השניים הקפידו להעניק קרדיט כתיבה זה לזה בכל השירים שכתבו. בין השניים התפתחה אותה עת תחרות ידידותית לכתיבת השירים המוצלחים ביותר של הלהקה, כשהפרס הנחשק ביותר הוא הזכות לשיר שיופיע על צד א' של תקליטוני הלהקה.
בשנים הראשונות להצלחת הלהקה (1963 - 1966) התגורר מקרטני בחדר בביתה של חברתו אותה עת, השחקנית המתחילה ג'יין אשר. יחסיהם של השניים ידעו עליות ומורדות, שחלקן תועד גם בשירים שכתב מקרטני בשנים אלו. היחסים הלכו והצטננו כאשר עבר מקרטני לבית משלו, ב-1966, ואחרי תקופת אירוסים קצרה ב-1968 באו לקצם.
מקרטני הפגין לאורך שנות פעילותה הראשונות של הלהקה עניין רב בתהליך ההקלטה ובחידושים מוזיקליים. למקרטני היה תפקיד חשוב בעיצוב האופן בו ניגן רינגו סטאר, חבר הלהקה, על התופים; באופן בו הוקלטה נגינת הבס בשירי הלהקה; ובהדרגה, לצידו של מפיקה המוזיקלי של הלהקה, ג'ורג' מרטין, גם בעיבוד המוזיקלי הכולל. תרומה חשובה נוספת של מקרטני לביטלס, לבד מהשירים שלהלחנתם היה שותף, הייתה התנסותו במוזיקה נסיונית, שחלק מלקחיה (לדוגמה, סרטי הקלטה מנוגנים לאחור) מצא את מקומו בתקליטי הלהקה.
הביטלס חדלו מהופעות חיות בסוף אוגוסט 1966. המהלך היה תחילה לצנינים בעיניו של מקרטני, אך לבסוף קץ גם הוא בהופעות בהן לא ניתן היה לשמוע את נגינת חברי הלהקה או להגיש באופן הולם את שיריה החדשניים והמורכבים יותר. אחרי הפסקת ההופעות נטלו חברי הלהקה חופשה ארוכה, במהלכה הלחין מקרטני את פס-הקול לדרמה הריאליסטית The Family Way (תקלה בירח הדבש).
עם שובה של הלהקה מן החופשה יזם מקרטני את הרעיון ליצור אלבום של הביטלס, שתוצג כלהקה אחרת, "להקת מועדון הלבבות הבודדים של סרג'נט פפר". מקרטני, הוגה הרעיון, היה הרוח החיה ביצירת האלבום החדשני, לו כתב את רוב השירים, ובעיצוב תצלום העטיפה המפורסם שלו.
זמן קצר אחרי צאת Sgt. Pepper, שזכה להצלחה אמנותית ומסחרית מסחררת, התאבד (ככל הנראה) מנהלה של הלהקה, בריאן אפסטיין. בחלל שנוצר נטל על עצמו מקרטני, לא תמיד לשביעות רצונם של חברי הלהקה האחרים, את תפקיד היוזם העיקרי. יוזמתו הראשונה הייתה יצירת סרט טלוויזיה אוונגרדי בשם Magical Mystery Tour (מסע הקסם המסתורי), שהיה אמור לתעד טיול בין אתרים בערי הפרובינציה של אנגליה, וברוח התקופה נוצר בלי תסריט מוגדר. הסרט הנסיוני הוקרן, שלא בטובתו, בזמן צפיית השיא של חג המולד של 1967, בניגוד מוחלט לאופיו, והוכתר ככישלון הראשון של הלהקה.
בשנת 1968 היו חברי הלהקה טרודים בענייניהם ובענייני אפל החברה החדשה שהקימו ביוזמת מקרטני. הניכור ההולך וגובר ביניהם ניכר באלבום הלבן - האלבום הכפול שהקליטו אותה שנה, ושחלקים ניכרים ממנו הוקלטו על ידי חברי הלהקה בנפרד, בלי שיתוף פעולה יצירתי ביניהם. לקראת תחילת 1969 יזם מקרטני פרויקט חדש, אף הוא נסיוני ברוחו, בו יקליטו חברי הלהקה את תקליטם החדש כשבמקביל מתועד תהליך ההקלטה במצלמות קולנוע. הפרויקט כונה Get Back ומתיעודו הקולנועי (בסרט Let it Be) ניתן להבחין במתח הרב שבין חברי הלהקה, במיוחד על-רקע תפקידו הדומיננטי של מקרטני בה, ועל רקע נוכחותה של אשתו הטרייה של לנון, יוקו אונו.
פירוק הביטלס.
אחרי כישלון פרויקט Let It Be חדלה הלהקה למעשה מלפעול כקבוצה מוזיקלית. מקרטני, שנישא זמן קצר לפני כן לחברתו האמריקנית לינדה איסטמן, סירב להשלים עם רוע הגזירה, ויזם פרויקט נוסף, שהיה לשירת הברבור של הלהקה. האלבום, Abbey Road, הוקלט שוב כשחברי הלהקה מתפקדים כקבוצה מוזיקלית, אך בידיעה ברורה כי קשה יהיה להמשיך בפעילות מעבר למאמץ חד-פעמי זה. סמוך לסוף ההקלטות אף הודיע לנון למקרטני כי מבחינתו הגיע סיפור הלהקה לסיומו.
אחרי הקלטת Abbey Road נקלע מקרטני למשבר אישי קשה. הוא הסתגר עם אשתו בחווה מרוחקת בסקוטלנד והרבה לשתות לשוכרה. בינו לבין שלושת חברי הלהקה האחרים פרץ קרע גלוי, על רקע מחלוקת בנושא מנהלה העתידי של הלהקה. לנון, האריסון וסטאר סברו כי יש לשכור את שירותיו של אלן קליין, שנודע ביכולתו לחתום על חוזי הקלטה מוצלחים במיוחד עבור לקוחותיו (עמם נמנו אז האבנים המתגלגלות). מקרטני, לעומת זאת, לא בטח בקליין וסבר כי יש לבחור בחותנו, עורך-הדין איסטמן, או באדם אחר שאינו קליין. המחלוקת הפכה לקרע גלוי, כאשר מקרטני סירב לצרף את חתימתו לחוזה הקלטות חדש לביטלס, בתנאים משופרים, לחמש שנים נוספות. מקרטני חש נבגד במיוחד כאשר נודע לו כי לנון וקליין חכרו את שירותיו של המפיק המוזיקלי פיל ספקטור, שייצור אלבום חדש לביטלס מחומריו הלא מוגמרים של פרויקט Get Back. מקרטני חש כי הבישול המחודש של השירים מעל בעקרונות שהיו מקובלים בלהקה, ואף לווה בפעולות נקמניות וקטנוניות מצד לנון.
מקרטני, שהקליט בביתו אלבום בו ניגן בכל הכלים, החליט לצאת לדרך חדשה, והכריז באפריל 1970 על פרישה מן הלהקה ועל הוצאת תקליט חדש, ימים ספורים לפני הוצאתו המיועדת של אלבומם האחרון של הביטלס, Let it Be
להקת כנפיים.
תקליטו הראשון של מקרטני אחרי פירוק הביטלס נקרא בפשטות McCartney. התקליט זכה להצלחה מסחרית ניכרת, אך גם לביקורת על ההפקה הבלתי-מהוקצעת שלו. תקליטו השני, Ram, היה מלוטש הרבה יותר בהפקתו, וזכה אף הוא להצלחה רבה. תקליטון מתוכו, עם השיר Uncle Albert/Admiral Halsey, הגיע למקום הראשון במצעדי המכירות בארצות-הברית. תקליט זה, ולצדו האלבום Imagine של לנון, היו גדושים התייחסויות ועקיצות הדדיות בין שני השותפים-ליצירה לשעבר, שניצבו עתה משני צידי המתרס בהתכתשות על נכסי להקת הביטלס.
מקרטני העדיף להימנע מתגובה ארסית ומהמשך ההתכתשות הפומבית עם לנון. בסוף 1971 הוא הקים להקה חדשה בשם Wings (כנפיים), בה היו חברים מקרטני ואשתו לינדה, דני ליין (לשעבר מלהקת המודי בלוז) והמתופף דני סייבל. הלהקה החדשה הוציאה תקליט צנוע, ללא פרסום מוקדם, בשם Wild Life, שזכה להצלחה צנועה. מטרתו העיקרית של מקרטני הייתה לנסות לשנות את תפישתו כחבר הביטלס לשעבר בלבד, וליצור לעצמו שם שאינו נסמך רק על תהילת העבר. מקרטני ולהקתו יצאו לסיור מאולתר באוניברסיטאות ובמכללות בבריטניה, בלי פרסום מראש וללא ביצוע של שירי הביטלס; ואחר כך לסיור ערים ממושך באירופה, כשהם נודדים באוטובוס פשוט, ומבצעים רק שירים של "כנפיים". מקרטני הוסיף לצעד זה הוצאת שני תקליטונים ב-1972 שזכו לאיסור השמעה ב-BBC: התקליטון Hi, Hi, Hi נאסר להשמעה בגלל שימוש בשפה גסה, ואילו Give Ireland Back to the Irish, שנכתב אחרי טבח יום ראשון העקוב מדם נאסר להשמעה בגלל המסר הפוליטי שלו.
במהלך 1972, בין מסעות ההופעות, הקליט מקרטני, עם גרסה חדשה ומורחבת של "כנפיים" (עם הגיטריסט הנרי מקאלוך כחבר חמישי), תקליט נוסף בשם Red Rose Speedway מקרטני הקדים והוציא, לפני הוצאת התקליט, תקליטון עם השיר My Love שהיה לקוח ממנו. התקליטון זכה להצלחה רבה, במיוחד בארצות הברית, והתווה את הכיוון להצלחה הגדולה אותה נחל גם Red Rose Speedway.