Kyuss estaba llegando a su fin y mientras John García hacía sus pinitos con Slo Burn, Josh Homme crea Gamma Ray y se dirige a Seattle para girar como guitarrista para unos de sus ídolos, Screaming Trees en la gira de Dust, momento dulce para la banda.
Dato curioso es que la primera vez que Queens of the Stone Age aparecen en disco es en un split compartido precisamente con Kyuss, como si fuera el anuncio de que de una legendaria banda surgiría una nueva promesa de la mano de su mayor cabeza pensante. Ya las tres canciones que aquí se incluyen apuntaban maneras y contaban con colaboraciones de Van Conner, el propio John García o Chris Goss, productor de confianza de QOTSA. Este EP histórico saldría en el sello Man´s Ruin especializado en la etiqueta «stoner rock» y encargado de editar las famosas Desert Sessions, de las que irían saliendo ideas que cuajarían en la banda de Homme.
En 1998 ve la liz el primer disco de las «reinas de la edad de piedra». El sonido pasa por añadir fuertes dosis melódicas al rock desértico que practicaba Kyuss con fuertes influencias de la sección más metálica del grunge (Soundgarden, Alice In Chains). En especial Homme parece esforzarse por lucir una voz bastante emparentada con la de Chris Cornell, por supuesto sin llegar a brillar de tal forma. Aunque el resultado es espectacular y la cítica lo celebra, la sensación es un tanto agridulce dada la mágica historia de los de Palm Springs.
Josh Homme comenzaría a destacar por su sentido del humor, acreditando en el libreto a Mike Johnson con «sofa» por instrumento o incluyendo a un tal Carlo como bajista que según reconoció era su «alter ego borracho». Teniendo en cuenta que mucho más adelante acabaría tocando la batería en un proyecto paralelo, el futuro de Homme como hombre orquesta resulta esperanzador. De momento aquí ese puesto lo cubría el también ex-Kyuss Alfredo Hernandez.
Cuando los dos miembros que por entonces componían la banda vieron un concierto de los Dwarves con su también antiguo compañero de Kyuss, Nick Oliveri desnudándose y enfrentándose al público, quisieron su carisma rebelde para la banda. Así que le incluyeron en la contraportada de un disco que presentaron en España dos veces, la segunda ya con Gene Troutman a la batería. Sin duda el comienzo de unas idas y venidas en la alineación que no han hecho sino ratificar que QOTSA no es ni más ni menos que Josh Homme y amigos.
Si en el primer disco la ruptura con su anterior disco no era tan patente, en el segundo, Rated R Homme se soltó la melena y la banda forjó un sonido propio y excitante cediendo protagonismo vocal a personalidades tan dispares como Nick Oliveri y el propio Mark Lanegan, desde entonces considerado miembro oficial aunque poco constante. La estelar participación de Lanegan recuperó para el rock una garganta maldita y privilegiada que sin duda hizo subir enteros la estima hacia la banda.
Si bien algunos de sus fans más heavies renegaron de un sonido a veces relajante (In The Fade), a veces esquizofrénico (Monster In The Parasol) o simplemente infeccioso y pegadizo (The Lost Art Of Keeping A Secret, Feel Good Hit Of The Summer). Las publicaciones británicas tan dadas a inflar los hypes hablaron de la banda como lo más grande en el rock americano desde Nirvana (NME dixit) y el público europeo comienza a apreciar este nuevo sonido y sobre todo comienzan a multiplicarse sus fans por la música en sí y no sólo fieles seguidores de Kyuss.
Se abre un filón comercial para la banda que se acerca cada vez más al mainstream también gracias a polémicas con gente como Terrorvision o Britney Spears. Este momento coincide con triunfos en directo de QOTSA como el de Rock In Rio, junto a bandas del nivel de Guns’n’Roses y REM o apariciones en recopilatorios, como la banda sonora de Heavy Metal 2000 en la que incluyeron «Infinity». Tras esto dieron una segunda gira europea esta vez con el acompañamiento de Mark Lanegan.
Parecía en serio pues lo de la voz de Screaming Trees con la banda de Homme. Así se demostró de nuevo en Songs for the Deaf un disco que les sitúa como el más auténtico relevo del sonido de los 90 y donde cabe desde su faceta más doom y machacona hasta el pop más perfecto. Mención especial para la colaboración de Dave Grohl, que recogió batería para este disco demostrando lo desapercibido que pasaba su talento en Nirvana y dejando en evidencia su nada despreciable labor al frente de Foo Fighters.
El estrellato muchas veces trae mal ambiente. Las actuaciones de la consiguiente gira en nuestro país no fueron del todo satisfactorias para parte de los fans, debido a problemas de sonido y de mala hostia por parte de un malhumorado Oliveri. Al parecer ese día el bajista salió pasado de absenta, situación que sumada a otras culminó meses más tarde en su expulsión de la banda. El bajista se refugió de nuevo con los Vandals y su proyecto Mondo Generator (nombre extraído de un tema de Kyuss). Por su parte Homme encontró una vía de escape haciendo de batería en Eagles of Death Metal banda de garage planteada como un divertimento junto a Jeese «the devil» Hughes y Tim Van Hammel de Millionaire.
También vió la luz un EP llamado Stone Age Complication cuyo título bien podría ilustrar el momento delicado por el que pasaba la banda. Recogía versiones de sus adorados Kinks, Subhumans y The Cramps, así como un remix de U.N.K.L.E. y dos temas que no aparecieron en los discos, «Born To Hulla» y «The Bronze».
Pero no era el fin de QOTSA ni mucho menos. Prescindiendo de Oliveri y manteniendo la presencia de Lanegan en poco más que anecdótica, Homme grabó un cuarto disco que sirvió para reafirmarle como compositor de nivel y demostró que los añadidos realzan su música pero el resultado es más que digno sin ellos. De hecho este Lullabies to Paralyze cuenta con colaboraciones de Shirley Manson (Garbage) y la novia de Homme, Brody Dalle (Distillers) que pasan bastante desapercibidas. Algo más atención recibe Bill Gibbons de los barbudos ZZTop que comparte duelo de gargantas rotas con Lanegan en Burn The Witch.
El mismo 2005 la banda editó un CD/DVD en directo, «Over The years and Through The Woods». La banda ha incorporado a una teclista, Natasha Shneider y la alineación se completa con Alain Johannes al bajo, Troy Van Leeuwen a la guitarra y Joey Castillo a la batería.
En 2006 Homme edita un segundo disco de Eagles of Death Metal incorporando miembros de QOTSA en la alineación, pese a no acompañar a Jeese «The Devil» Huges en la mayor parte de la gira. Su prioridad sigue siendo Queens of The Stone Age, con quienes ya en mayo de 2007 edita su quinto y hasta el momento más polémico disco, «Era Vulgaris» en el que muchos ven una ligera pérdida de inspiración. El guitarrista se embarcará en aventuras como Them Crooked Vultures con Dave Grohl y John Paul Jones (Led Zeppelin) y seguirá girando con QOTSA, incluyendo una gira de recuerdo a su primer disco. Mientras tanto, sus compañeros de Kyuss invocan una reunión en la que Homme prefiere no participar.