Fondato nel 1967 a San Francisco da Jann S. Wenner (tuttora editore) e dal critico musicale Ralph J. Gleason, Rolling Stone venne inizialmente identificato con la scena hippie, per poi prendere le distanze dal mondo delle riviste underground e dall'orientamento politico radicale delle stesse, abbracciando anche canoni giornalistici più tradizionali. Ma la politica rimase un elemento fondamentale della rivista, che ne fece il suo marchio nei primi anni settanta grazie al gonzo journalism di Hunter S. Thompson.
La rivista, che lanciò Cameron Crowe e tanti altri, divenne tanto influente che i Dr. Hook & The Medicine Show intitolarono una loro canzone (scritta da Shel Silverstein) Cover of the Rolling Stone ("La copertina del Rolling Stone").
Negli anni ottanta, pur continuando a ospitare giornalisti e scrittori che erano diventati ormai icone, come lo stesso Thompson, Rolling Stone assunse alcune caratteristiche che aveva precedentemente evitato. Si spostò a New York nel 1976, e molti considerano questa data l'inizio del cambiamento della rivista. Molti collaboratori andarono via e molti altri firmarono, e le copertine si orientarono sempre di più alle star del cinema. Tra il 1980 e il 1982 una sorta di spin-off fu edito dalla sorella di Jann Wenner, Kate. Secondo il libro Rolling Stone Magazine di Robert Draper, fu a metà degli anni '80 che Rolling Stone smise di lanciare le mode musicali per cominciare a seguirle. Alla fine degli anni '90 la rivista pubblicò una foto della nascente popstar Britney Spears, che fece molto scalpore anche perché mostrò chiaramente che la diciassettenne aveva subito un'operazione di "gonfiamento" chirurgico.
Nei primi anni del 2000, dovendo affrontare la concorrenza (Maxim, FHM e altri), Rolling Stone si reinventò, accogliendo Ed Needham, ex editore di FHM. La rivista cominciò a rivolgersi a un pubblico più giovane e a orientarsi molto più spesso al sesso, parlando ad esempio di giovani sexy-star della TV o del cinema, o ancora della Pop music. Alcuni lettori di lunga data denunciarono il cambio di rotta della rivista, affermando che Rolling Stone era diventato un superficiale tabloid e aveva tradito la sua storia di astuto osservatore musicale e culturale, enfatizzando lo stile a scapito della sostanza. È comunque da quel momento che Rolling Stone ha ripristinato il suo mix originale di contenuti, ospitando di nuovo inchieste politiche (da una prospettiva fieramente orientata a sinistra), con una notevole crescita nelle vendite. L'attuale editore è Will Dana.
Per festeggiare quello che la rivista chiama il "50esimo Anniversario del "Rock" (2004), Rolling Stone iniziò a pubblicare degli elenchi che individuassero le pietre miliari della storia del rock. Questi elenchi destarono molte discussioni tra i critici. Nel 2003 fecero la loro comparsa "The 100 Greatest Guitarists of All Time" (I 100 più grandi chitarristi di tutti i tempi) e "The 500 Greatest Albums of All Time" (I 500 più grandi album di tutti i tempi); l'anno successivo fu la volta dei "50 Moments That Changed the History of Rock & Roll" (I 50 momenti che hanno cambiato la storia del rock'n'roll) e di "The 500 Greatest Songs of All Time" (Le 500 più grandi canzoni di tutti i tempi). Uscì anche "The Rolling Stone Immortals", un elenco dei 100 migliori artisti dei nostri tempi, e "The 100 Greatest Singers Of All Time, riguardante i 100 migliori cantanti del '900, lirica esclusa.
La lista dei 100 migliori chitarristi destò una forte reazione , tra i lettori e gli appassionati del genere , non solo per chi era presente (Kurt Cobain davanti a Brian May, David Gilmour e Mark Knopfler), ma anche per chi non c'era: Eric Johnson, Joe Satriani, Steve Vai, Slash e altri. Ma anche perché il termine migliore significa una prestazione in senso lato ,difficile da dimostrare in campo musicale con preferenze così soggettive .
Il 7 maggio 2006 Rolling Stone pubblicò il suo speciale per la 1000esima copertina. Influenzata da quella di Sgt. Pepper's Lonely Hearts Club Band dei Beatles, la cover ospita le più celebri star delle copertine di RS.
Pur essendo una rivista di intrattenimento, Rolling Stone ha sempre cercato un ruolo nel dibattito politico. Le sue radici hippie le hanno dato una prospettiva editoriale liberale. Il celeberrimo Hunter S. Thompson fu il suo più grande corrispondente politico, e curò la sezione National Affairs. Matt Taibbi prese il suo posto alla sua morte. La rivista ha criticato aspramente l'amministrazione Bush.
Nel numero del 4 maggio 2006, RS pubblicò un articolo di Sean Wilentz, storico della Princeton University, in cui Bush era definito "probabilmente il peggior presidente della storia", con una "combinazione di impotenza, pigrizia e inettitudine per questo lavoro.
Prima delle elezioni presidenziali del 2004, Rolling Stone dedicò una copertina a John Kerry, con il quale si schierò apertamente. Anche Bill Clinton e Al Gore erano stati in copertina.
Su RS fu pubblicato anche un articolo di Robert Kennedy Jr., spesso citato da Clinton, in cui si afferma che Bush ha imbrogliato alle elezioni del 2004.
Rolling Stone è ampiamente considerato la principale forza promozionale per la musica nella cultura americana, insieme a MTV. Viene citato spesso in molte opere, ad esempio nel film semi-autobiografico Quasi famosi di Cameron Crowe e nel cult movie Alta fedeltà, tratto dal romanzo di Nick Hornby. Nel film Cars - Motori ruggenti, invece, la rivista viene chiamata Rolling Tire. Alla fine di Prima o poi me lo sposo Drew Barrymore legge un numero di Rolling Stone con Billy Idol in copertina. Si tratta del n. 440, del 31 gennaio 1985: il film è ambientato in quell'anno.
Sono di RS, inoltre, molte delle copertine più controverse della cultura pop: una delle più discusse ritrae una allora diciassettenne Britney Spears in una posa da Lolita. Quel numero suscitò numerose voci riguardo a delle fantomatiche protesi al seno della cantante, che smentì.
L'attuale logo della rivista, creato da Rick Griffin, fu usato come base per le immagini promozionali del film School of Rock.
RS, inoltre, è considerato una delle riviste più influenti per quanto riguarda le recensioni cinematografiche.
Come molti altri Paesi del mondo, anche l'Italia ha la sua edizione di RS. Nato nel novembre 2003, Rolling Stone Italia è stato concepito da Andrea Cagno e David Moretti e diretto da Michele Lupi e Carlo Antonelli fino al 2006; la direzione è attualmente in mano al solo Antonelli. Al fallimento della capogruppo francese dell'ex editore IXO Publishing, RS Italia fu subito oggetto di contesa da parte di vari editori; poté mantenere il suo carattere di rivista indipendente grazie all'attuale editore, Quadratum.
Rolling Stone Italia nasce con delle caratteristiche peculiari che conserva tutt'ora: è una rivista patinata di grande formato, mensile (anziché quindicinale come in America), dedica grande spazio alla celebrazione di miti del rock (ripescando spesso vecchi articoli del Rolling Stone americano), e altrettanto a quelle che considera giovani promesse o talenti. Ospita editorialisti di una certa fama (Giorgio Gherarducci, Enrico Ghezzi, Massimo Coppola, Daniele Luttazzi per un lungo periodo), scrittori (Niccolò Ammaniti vi pubblica il romanzo a puntate Il libro italiano dei morti) e fumettisti (ha ospitato il fumetto a puntate Quarantasei, di Milo Manara e Valentino Rossi). RS Italia pubblica con frequenza inchieste politiche, come nella tradizione della rivista madre americana. Si occupa di arte e cultura di massa, e ha sempre un'ampia sezione dedicata a diversi stili di vita, definiti per qualche motivo, e in base allo spirito con il quale sono vissuti, rock & roll (Rock & Roll Style). Pubblica numerosi servizi fotografici e/o di moda e si mostra particolarmente attenta alla veste grafica. Tra le piccole rubriche che caratterizzano l'edizione italiana, si notano Funny Kingston (trafiletto mensile sulle droghe e, più in generale, su tutto ciò che provoca dipendenza) e Lo straniero, in cui ogni mese Joe Levy, vicedirettore di Rolling Stone USA, recensisce in inglese tre album di musicisti italiani. Una caratteristica che non passa inosservata è la massiccia presenza di materiale pubblicitario di grandi stilisti o case di moda.
Rolling Stone Italia ha pubblicato alcuni degli speciali storici di RS USA: I 50 momenti più importanti della storia del rock, I 500 migliori album di tutti i tempi e l'edizione italiana dello speciale celebrativo uscito in occasione della 1000esima copertina americana.
Curiosamente, per anni il sito di RS Italia non ha avuto alcun tipo di contenuto multimediale; si limitava, di mese in mese, a presentare il sommario della rivista, senza peraltro pubblicizzarne le uscite speciali. Nel settembre 2007 è stato inaugurato il nuovo sito.
Il numero di dicembre 2009 mette in copertina Silvio Berlusconi definendolo personaggio rock star dell'anno. Il fatto ha suscitato grande disappunto tra gli stessi lettori del magazine. L'anno precedente era stato designato lo scrittore Roberto Saviano.