באנגליה נשא האלבום את שם הלהקה, בעוד בארצות הברית, נשא את השם "England's Newest Hit Makers". האלבום כלל ברובו גרסאות כיסוי לשירי אר אנד בי ובלוז בנוסף לשיר מקורי "(Tell Me (You're Coming Back" אותו כתבו ג'אגר וריצ'רדס. בנוסף, ניתן קרדיט לשני שירים נוספים באלבום ל"Nanker Phelge"" - שם בדוי שהיה מקובל בין השנים 1963–1965 וסימל עבודה משותפת של חברי הלהקה. עטיפת האלבום שעוצבה לפי הנחיותיו של אולדאם, נטולה כל אזכור לשם התקליט ולשמה של הלהקה, קונספט שהיה נחשב חריג מאוד לאותה תקופה.
על אף שהייתה אלמונית יחסית מחוץ לתחומי אנגליה, יצאה הלהקה ביוני 1964 למסע הופעות ראשון בארצות הברית, אשר הוגדר על ידי ויימן כ"אסון". באותה תקופה הופיעו חברי הלהקה במספר תוכניות טלוויזיה דוגמת "המופע של אד סאליבן" ו"הוליווד פאלאס", שם המנחה, דין מרטין, התבדח מהמראה שלהם שכלל שיער ארוך, אשר נחשב לפרובוקטיבי.
ב-17 באוקטובר 1964, הוציאה הלהקה את אלבומה השני "12X5", אשר הופץ בארצות הברית בלבד. בדומה לאלבום הבכורה, כלל אלבום זה בעיקר גרסאות כיסוי של אמנים דוגמת צ'אק ברי, ביחד עם שלושה שירים מקוריים של ריצ'רדס וג'אגר ושני שירים שכתבו במשותף חברי ההרכב כולו. הלהיט הגדול ביותר באלבום הוא גרסת הכיסוי לשירו של בובי וואמק "It's All Over Now", שהיה לשיר הראשון של הלהקה שהגיע למקום הראשון במצעדים באנגליה.
לאחר יציאת האלבום, יצאה הלהקה לסיבוב הופעות שני בארצות הברית. בעקבות מהומה שפרצה באולפן במהלך הופעתם ב"מופע של אד סאליבן", נשבע סאליבן כי הלהקה לעולם לא תופיע יותר בתוכניתו. עם זאת, בעקבות העלייה בפופולריות שלה, הופיעה הלהקה במהלך השנים עוד מספר פעמים בתוכנית.
1967-1965: הצלחה מקצועית והסתבכויות משפטיות.
ב-15 בינואר 1965, הוציאה הלהקה את אלבומה "Rolling Stones No. 2", שהגיע למקום הראשון במצעדים באנגליה. האלבום, שיצא תחת שם זה באנגליה בלבד, כלל גרסאות כיסוי לשירי רית'ם אנד בלוז ישנים בהם "Everybody Needs Somebody to Love" של סולומון בורק, אך כלל גם שירים מקוריים פרי עטם של ג'אגר וריצ'רדס. חודש לאחר מכן, יצא בארצות הברית האלבום ""The Rolling Stones, Now!", אשר כלל שבעה שירים שהופיעו באלבום הלהקה בגרסה הבריטית.
ב-30 ביולי 1965, יצא בארצות הברית אלבומה הרביעי של הלהקה "Out of Our Heads"". האלבום כלל שבעה שירים מקוריים, ביניהם השיר "(I Can't Get No) Satisfaction", אשר זכה להצלחה ענקית ונחשב עד היום לאחד מלהיטיה הגדולים של הלהקה. היה זה אלבומה הראשון של הלהקה שהעפיל למקום הראשון במצעד "200 האלבומים הנמכרים ביותר" של מגזין המוזיקה בילבורד.
ב-24 בספטמבר 1965 הוציאה הלהקה באנגליה אלבום בשם זהה, על אף שהיה שונה מבחינת רשימת השירים.
ב-4 בדצמבר 1965, יצא בארצות הברית אלבומה החמישי של הלהקה ""December's Children (And Everybody's"). האלבום כלל מספר להיטים, בניהם הסינגל ""Get Off of My Cloud".
ב-15 באפריל 1966, יצא באנגליה אלבומה "Aftermath" וכעבור כחודשיים יצא גם בארצות הברית. האלבום, שהגיע לראש המצעדים בבריטניה ולמקום השני בארצות הברית, כלל בפעם הראשונה אך ורק שירים מקוריים שנכתבו בידי ג'אגר וריצ'רדס, ביניהם השיר באורך 12 הדקות, "Going Home"". כן נכללו באלבום שירים בולטים נוספים בהם" "Under My Thumb" ו- "Paint It Black", אשר יצא בגרסה האמריקאית בלבד וההעפיל ביוני 1966 לפסגת מצעד הסינגלים בארצות הברית.
ב-10 בדצמבר 1966, יצא "Got Live If You Want It!", אלבום ההופעות הראשון של הלהקה.
ב-20 בינואר 1967, יצא אלבום האולפן החמישי של הלהקה באנגליה "Between the Buttons". כעבור כחודש יצא האלבום גם בארצות הברית. בגרסה האמריקאית נכללו שני שירים שלא הוכנסו לגרסה הבריטית והפכו עם הזמן ללהיטים גדולים - "Ruby Tuesday" ו-"Let's Spend The Night Together"". היה זה אלבומה האחרון של הלהקה שיצא בנפרד בבריטניה ובארצות הברית. בשנת 2012, דורג האלבום (בגרסתו האמריקאית) במקום ה-357 ברשימת 500 האלבומים הגדולים בכל הזמנים של מגזין המוזיקה "הרולינג סטון".
בעקבות מאמר בן שלושה חלקים שפורסם בצהובון הבריטי "ניוז אוף דה וורלד", אשר עסק במעורבותם של כוכבי רוק בצריכת סמים ואלכוהול במהלך מסיבות אותן ארגנו חברי להקת "המודי בלוז", החלו הרשויות באנגליה לרדוף אחר שלושה מחברי הלהקה - ג'אגר, ריצ'רדס וג'ונס, לאחר פרסום חלקו השני של המאמר ב-5 בפברואר 1967 שעסק בהתנהלות הלהקה.
ב-12 בפברואר 1967, בעקבות מידע שקיבלה מעורכי הצהובון, ערכה משטרת סאסקס פשיטה על ביתו של ריצ'רדס. על אף שלא בוצעו מעצרים במהלך הפשיטה, הורשעו ג'אגר וריצ'רדס בגין עבירות סמים. בשל חשש ממעצר, ברח מנהל הלהקה אולדאם לארצות הברית.
במרץ 1967, יצאו ריצ'רדס וג'ונס לחופשה במרוקו ביחד עם מספר חברים, בהם הזמרת מריאן פיית'פול וחברתו של ג'ונס - הדוגמנית והשחקנית האיטלקייה אניטה פלנברג. לאחר אלימות חוזרת ונשנית מצד ג'ונס ומתח רב שנוצר בין השניים במהלך החופשה, החליטה פלנברג לחזור לאנגליה ביחד עם ריצ'רדס. השניים המשיכו לנהל מערכת יחסים רומנטית שארכה כ-12 שנה, במהלכה נולדו להם שלושה ילדים. מערכת יחסים זו יצרה קרע בין ג'ונס לריצ'רדס והיוותה אחד מהגורמים לפרישתו מהלהקה של ג'ונס כעבור כשנתיים.
על אף המתיחות בין ג'ונס לריצ'רדס, יצאה הלהקה באותו חודש למסע הופעות באירופה שארך כחודשיים. במהלך המסע הופיעה הלהקה לראשונה במספר מדינות באירופה, ביניהן פולין, יוון ואיטליה.
ב-10 במאי 1967, עצרה המשטרה את ג'ונס לאחר פשיטה על ביתו. כנגד ג'ונס הוגש כתב אישום על החזקת מריחואנה. באותו היום הוגש כתבי אישום גם כנגד ג'אגר וריצ'רדס, אשר הורשעו כעבור כחודש וחצי. על ג'אגר נגזר עונש מאסר של שלושה חודשים בגין החזקת ארבעה כדורי אמפטמין. על ריצ'רדס נגזרה שנת מאסר בגין כך שאיפשר צריכת סמים במהלך המסיבה שנערכה בביתו בחודש פברואר.
בעקבות החלטת בית המשפט והעונשים החמורים שהוטלו על השניים, נוצר הד ציבורי רב, בטענה שחומרת הענישה נקבעה לאור היותן של הנאשמים אישיים מפורסמים. במסגרת מאמר המערכת שפרסם עיתון הטיימס, אשר כותרתו הייתה "מי שובר פרפר על גלגל?", טען עורך העיתון ויליאם ריס-מוג כי עונשו של ג'אגר היה חמור הרבה יותר בהשוואה לכל עונש אותו היה מקבל כל אדם אנונימי שהיה מבצע עבירה דומה.
במהלך ההמתנה לתוצאות הערעור שהגישו ג'אגר ור'יצ'רדס, הוציאה הלהקה את הסינגל "We Love You", כמחווה למעריציהם על תמיכתם במהלך אותה תקופה. השיר עצמו נפתח בצליל של דלת תא כלא נסגרת בעוד הקליפ שהופק עבור השיר כולל רמזים הנוגעים למשפטו של אוסקר ויילד, אותו גילם ג'אגר.
ב-31 ביולי 1967, התקבל ערעורו של ריצ'רדס והוא זוכה בעוד עונשו של ג'אגר הומתק למאסר על תנאי. בנובמבר 1967 החל משפטו של ג'ונס שערך כחודש. בית המשפט הטיל על ג'ונס עונש מאסר על תנאי למשך שלוש שנים וקנס של 1000 ליש"ט. בנוסף, נשלח ג'ונס לקבלת טיפול מקצועי וגמילה מסמים ואלכוהול.
ב-8 בדצמבר 1967, הוציאה הלהקה את האלבום "Their Satanic Majesties Request". האלבום, שאופיין בסגנון פסיכדלי (הן בעיצוב העטיפה על ידי הצלם מייקל קופר והן בסגנון השירים), היה לראשון שיצא בגרסה אחידה באנגליה ובארצות הברית. האלבום, שיצא זמן קצר לאחר סרג'נט פפר של הביטלס, היה התשובה הפסיכדלית של הלהקה למהפכת ילדי הפרחים. בין שירי האלבום הבולטים, ניתן למצוא את "She's A Rainbow" ואת "In Another Land", שהיה לשיר הראשון של הלהקה שאותו כתב וביצע ביל ויימן.
על אף הצלחת האלבום, החליטו חברי הלהקה לא לבצע את השירים שבו בהופעותיהם, ועם השנים הוא נינטש לאנחות. זמן מה לאחר מכן פוטר אולדהם על רקע חיכוכים פנימיים, שהחלו בזמן הקלטת האלבום, ובמקומו נשכר מנהל חדש, אלן קליין.
באוטוביוגרפיה שלו "חיים", כתב ריצ'רדס כי לאחר הוצאת האלבום, הייתה ירידת מתח בלהקה והייתה תחושה כי "נגמר להם הדלק". בהמשך ציין ריצ'רדס כי הקאמבק של הלהקה הגיע בעקבות הצטרפותו של מפיקה החדש ג'ימי מילר שהפיח רוח חדשה בלהקה.
בתקופה זו, פחתה מעורבותו של בריאן ג'ונס בלהקה. בעקבות שימוש מתמשך בסמים ואלכוהול, אושפז ג'ונס בבתי חולים, והריחוק בינו לבין חברי הלהקה יצר מריבות בלתי פוסקות ולתחושת ניכור מצידו.
1972-1968: מותו של ג'ונס, פסטיבל אלטמונט, "Let It Bleed" ו-"Sticky Fingers".
ב-24 במאי 1968, הוציאה הלהקה את הסינגל "Jumping Jack Flash". בקרב מבקרי מוזיקה שונים, סימל השיר את חזרתה של הלהקה לשורשי מוזיקת הבלוז (דלתא בלוז) שאפיינה אותה בתחילת דרכה וזאת במעבר מסגנון הפופ הבארוקי והמוזיקה בעלת המאפיינים הפסיכדלים שבאה לידי ביטוי באלבומים האחרונים של הלהקה - "Aftermath" (משנת 1966), ""Between the Buttons" ובעיקר "Their Satanic Majesties Request"" (משנת 1967). השיר זכה להצלחה גדולה ונחשב לשיר המבוצע ביותר בהופעותיה של הלהקה עד היום.
ב-6 בדצמבר 1968, הוציאה הלהקה את האלבום "Beggars Banquet". השיר הבולט באלבום באלבום הוא "Sympathy for the Devil", שזכה להצלחה גדולה ודורג במקום ה-32 ברשימת "500 השירים הגדולים בכל הזמנים" של הרולינג סטון. שיר בולט נוסף באלבום הוא "Street Fighting Man", שנכלל אף הוא ברשימת השירים הגדולים של המגזין.