Antes do surgimento dos Queens of the Stone Age, existia uma banda californiana chamada Kyuss que partiu do completo anonimato para tornar-se ícone cult da cena heavy metal americana. No entanto, apesar da popularidade os Kyuss acabaram em 1995 e o líder e guitarrista Josh Homme mudou-se para Seattle. Em Seattle, Josh ingressou nos Screaming Trees como segundo guitarrista durante o tour do álbum Dust de 1996. A partir de 1997 com o declinio dos Sreaming Trees, Josh encontra tempo suficiente para trabalhar num projecto próprio. Foi o início da série Desert Sessions, projecto que lhe permitiu expressar-se com maior liberdade e experimentalismo. Logo de seguida, Josh resolve criar outra banda, os Queens Of The Stone Age.
O primeiro disco, homonimo, foi financiado pela própria banda e acabou lançado em Setembro de 1998 pela editora Loosegroove, propriedade do Stone Gossard, guitarrista dos Pearl Jam. O álbum teve uma repercussão impressionante e ajudou a fixar o nome dos QOTSA como uma das grandes promessas do rock atual.
Em Junho de 2000 é lançado "Rated R", desta vez pela Interscope, uma editora de maior dimensão. Os Queens of the Stone Age embarcaram num exaustivo tour de dois anos pelo mundo todo, incluindo um memorável concerto no Rock in Rio em janeiro de 2001, onde Oliveri se apresentaria em palco completamente nu.
No ano seguinte a banda já estava em estúdio preparando o terceiro disco "Songs For The Deaf". Album esse que contou com a participação do ilustre Dave Grohl, ex-Nirvana e líder do Foo Fighters na bateria. Deste album saiu o single mais mediático da banda "No one knows".
Em 2005 e após alguns momentos conturbados da banda,(com vários abandonos) eis que surge "Lullabies to Paralyze", quarto álbum da banda,onde vem à tona toda a capacidade dos artistas comporem melodias mais densas, sombrias e perturbadoramente pesadas. Diz ke dissera ke é o melhor album da banda.
Agora entramos numa nova era, a "Era Vulgaris". Este novo album da banda editado em Junho de 2007 tem colaborações de Jesse Hughes do Eagles Of Death Metal, Trent Reznor do Nine Inch Nails e Julian Casablancas dos Strokes. Um disco bastante alternativo, mas muito bom. Um belo exemplo de como deve ser um grande album de Rock. Talvez melhor que "Songs For The Deaf".

Depois de tantas saidas e entradas esta é a actual formação:
Josh Homme - voz, guitarra e baixo (desde 1997)
Troy Van Leeuwen - guitarra, baixo e Lap Steel (desde 2002)
Joey Castillo - bateria (desde 2002)
Michael Shuman - baixo (Wires On Fire)
Dean Fertita - teclado (The Raconteurs)
Aqui fica um dos singles, "3's & 7's".
Enjoy it, Five Horizons team!!!