Songs for the Deaf ha conquistato pubblico e critica, Josh Homme è diventato una star, ma purtroppo questo periodo più che positivo non dura a lungo per la band; innanzitutto, Homme caccia via Oliveri "per divergenze artistiche" (in seguito invece rivelerà che Oliveri aveva importunato sessualmente Brody Dalle, fidanzata di Homme e cantante dei Distillers), poi si imbarca in un progetto solista relativamente trascurabile, gli Eagles of Death Metal (che nel 2004 pubblicano il loro primo disco, intitolato Peace, Love and Death Metal); infine decide finalmente di circondarsi, come sempre, di vari amici musicisti per incidere il quarto album a nome Queens of the Stone Age.
Per stabilire una sorta di filo conduttore con la precedente opera, Homme decide di intitolare il disco Lullabies to Paralyze, frase presente nel testo di Mosquito Song (ultima traccia di Songs for the Deaf).
L'apporto di Mark Lanegan, stavolta, è minimo: fa solamente la seconda voce in Medication, Tangled up in Plaid, e Long Slow Goodbye, poi parte in tour con la sua band; questo solleverà voci sul fatto che nemmeno Lanegan faccia più parte del gruppo di Homme.
Josh chiama invece a dar man forte al suo progetto Troy Van Leeuwen (ex A Perfect Circle), Joey Castillo, e Alain Johannes (già collaboratore nella canzone Hangin' Tree sul precedente album).
Però stavolta qualcosa non ingrana: la produzione è molto più pulita e rock nel senso tradizionale del termine (più adatta ad un gruppo new-wave che ad un gruppo stoner), l'alchimia che caratterizzava Songs for the Deaf è svanita, le sperimentazioni melodiche di Rated R sono lontane anni luce da ciò che frulla in testa a Homme, e il primo album è solo un bel ricordo.

Dopo una pacata ninna-nanna country che fa da introduzione (This Lullaby) incontriamo la trascinante Medication, che apre l'album alla perfezione, rasentando nuovamente il "robot rock" degli esordi, stavolta in modo più catchy e melodico; poi la demenziale ma potente Everybody Knows That You Are Insane, e a ruota le carucce Tangled up in Plaid e Burn the Witch; il disco continua su questa linea abbastanza buona con le più incisive In My Head e Little Sister (quest'ultima il primo singolo, azzeccato per l'equilibrio perfetto tra melodicità e potenza), ma poi precipita negli abissi con una serie di quattro pezzi troppo lunghi e trascurabilissimi (vuoi per ripetitività, vuoi per noiosità, vuoi per il senso di disinteresse che procurano).
Dobbiamo aspettare fino a Broken Box, che riporta per un attimo alle atmosfere di Rated R; peccato che sia seguita da un altro episodio minore e ripetitivo, You Got a Killer Scene There, Man... (retta solamente dai cori vocali, a cui partecipano Brody Dalle dei Distillers, Shirley Manson dei Garbage, il già citato Mark Lanegan, e Chris Gross), prima di arrivare alla traccia conclusiva Long Slow Goodbye, ballad affascinante e dalle molte caratteristiche tipicamente qotsiane.

Questo album, fondamentalmente, non convince. Probabilmente il mediocre risultato è dovuto al fatto che Josh Homme stavolta non abbia voluto (o non abbia potuto) costruire alcuna alchimia con i suoi collaboratori, e si sia concentrato solamente su se stesso; buona parte delle tracce trasudano infatti egocentrismo da ogni poro, ed evidentemente queste cose incidono negativamente anche su grandi musicisti come Homme.
A ciò bisogna anche aggiungere che, purtroppo, il calo di idee e di creatività è evidente. E la produzione quasi pop-rock non aiuta di certo, smorzando i pochi spunti aggressivi e facendo rimpiangere le schitarrate e il drumming di Songs for the Deaf.
Insomma: non è un lavoro da cestinare, ma nemmeno da elogiare; vista la caratura dei tre dischi precedenti, era certamente lecito aspettarsi qualcosa di più.
Peccato, un'occasione sprecata.