Desde la disolución de Kyuss en 1995, Josh Homme ha buscado su camino y su vena artística como guitarrista y como compositor. En un primer momento, se translada a Seattle y comienza a tocar con Screaming Trees, actuando como segundo guitarrista. Mark Lanegan, el cantante de Screaming Trees, le devolverá el favor cantando algunos temas del disco Rated R, incluida la dirección vocal de "In the Fade".

Hacia 1997 Josh vuelve a ponerse en contacto con su antiguo amigo Nick Oliveri (que había estado tocando en la banda de punk Dwarves) y con el baterista de la última etapa de Kyuss, Alfredo Hernández. Vuelven a Palm Desert para crear un nuevo sonido, pero con la idea clara de no ser una segunda parte de Kyuss.

El trabajo de Queens Of The Stone Age le lleva a crear a Josh lo que llamaría el robot rock. Música heavy, marcando los golpes de guitarra que tienden a economizarse, baterías mínimas, muy básicas y con repeticiones de los temas al más puro estilo trance. Ponen el dinero para su álbum presentación Queens Of The Stone Age, encarando el camino de lo que iba a ser el rock del nuevo milenio. Las radios alternativas pincharon un montón el tema If Only y la revista Rolling Stone colocó a Queens Of The Stone Age como "una de la diez bandas más importantes del rock y del heavy del momento".

Josh, Nick, Alfredo y Dave Catching realizan una gira que duraría cerca de dos años en la que actuarían junto a grupos como Bad Religion, Rage Against the Machine o The Smashing Pumpkins.

Josh continua experimentando y grabando disco en paralelo, creando la serie Desert Session para el sello Man's Ruin Records. Esta serie le llevo a colaborar con gente de Monster Magnet, Soundgarden, Fu Manchu y otros miles de artistas que se dejaron caer por los estudios Mojave Desert.

Rated R se grabó con dos maquinas analógicas de 16 pistas en los estudios Sound City de Los Ángeles, los mismos estudio donde Kyuss creó Blues for the Red Sun, Sky Valley y And the Circus Leaves Town. Rated R fue producida por Josh y Chris Goss (Masters of Reality) y dirigido por Trina Shoemaker.

2005 es el año para un nuevo disco, Lullabies to paralyse.