Durante il tour successivo al disco Rated R , Josh Homme stringe amicizia con Dave Grohl (ex batterista dei Nirvana e leader dei Foo Fighters), che gli confessa di aver sempre voluto suonare la batteria per un gruppo come i Queens of the Stone Age.
Josh non se lo fa ripetere due volte, e lo recluta per la registrazione del suo terzo lavoro sotto il monicker Queens of the Stone Age. Inoltre tiene al basso e alla seconda voce Nick Oliveri, e recluta nuovamente (stavolta a presenza fissa) Mark Lanegan, l'ex leader degli Screaming Trees.
Questa alchimia è davvero vincente, e dà vita a Songs for the Deaf, un vero e proprio inno al "rock'n'roll duro e puro" nell'anno di grazia 2002, che diventa in breve uno straordinario successo di pubblico e critica.
L'album è praticamente un unicum in cui le tracce si susseguono tramite un intelligente stratagemma, ovvero quello di un finto airplay radiofonico: a conclusione di ogni canzone ci sono infatti degli imprecisati DJ che introducono la traccia successiva.
A livello qualitativo tutte le canzoni sono degne di nota, e non si hanno cali di ritmo o di creatività per l'intera durata dell'album; i suoni di produzione sono volutamente più sporchi che in Rated R, perché devono dare sensazioni del tutto diverse, ma a livello compositivo le tracce sono tutte curate e raffinate, pur mantenendo un'energia primordiale davvero trascinante.

Si parte con la micidiale Millionaire, un'amplificazione delle sonorità più heavy dell'album di debutto, per giungere al primo singolo No One Knows (divertente, scanzonata, originale), per poi passare alla straordinaria First It Giveth e all'altrettanto bella A Song for the Dead, dalle ritmiche imprevedibili e affascinanti.
The Sky Is Fallin' riprende strutture da canzone rock dell'era pre-grunge e le modifica in melodie folli il cui ritornello è un continuo stop-and-go; Six Shooter è un brevissimo e violento sfogo hardcore di Nick Oliveri; Hangin' Tree è un episodio minore, che però ci introduce la magnifica Go with the Flow, una canzone davvero spettacolare e trascinante dall'inizio alla fine, una vera perla.
Qui si conclude la prima parte, più urlata, del disco, e si apre la seconda, più intimista (ma anche complessivamente meno interessante); troviamo la quasi new-wave dal gusto retrò di Gonna Leave You, la melodicissima Do It Again, l'incrocio tra blues e Stoner di God Is in the Radio, la trascinante ballata d'amore Another Love Song, ed infine un'altra perla: la bella, lugubre e raffinata A Song for the Deaf, dalle atmosfere cupe ed opprimenti.
A fine della traccia c'è un'autocitazione (una parodia di Feel Good Hit of the Summer), e poi parte una canzone nascosta: Mosquito Song, la traccia 15, una dolcissima ballata che vede il contributo di Paz Lenchantin (all'epoca negli A Perfect Circle) agli archi.

Per quanto riguarda Dave Grohl, il suo drumming è il pilastro del disco: esemplare, spettacolare, un modo di suonare unico che lo conferma uno dei batteristi rock più bravi in circolazione; le sue soluzioni sono geniali specie in pezzi come First It Giveth, Go with the Flow e A Song for the Dead, e la produzione sonora per la sua batteria è perfetta.
Mark Lanegan invece contribuisce con quel tocco di maestria e tecnica qualitativa in più, che non fa mai male, ed è lui il principale artefice dei gioielli No One Knows, A Song for the Dead, e A Song for the Deaf.
Davvero un peccato che questa alchimia sia durata solo per un album, e poi Lanegan e Grohl siano tornati ai loro progetti principali.
C'è da segnalare che la freschezza e il successo di vendite di questo album (il cui gradimento e originalità stanno principalmente nell'aver portato lo Stoner alle masse in una formula perfetta e vincente) hanno contribuito a dare la mazzata finale al mercato statunitense del nu-metal (già ormai in crisi e costretto a raschiare il fondo del barile), ribadendo come anche nel terzo millennio si possa fare del grande rock'n'roll, senza troppi fronzoli, e registrare un album potente e originale.