Formata din membrii trupei Kyus, emblematica pentru stilul stoner rock, Queens of the Stone Age ii reuneste pe vocalistul/chitaristul trupei Josh Homme, bateristul Alfredo Hernandez, basistul Nick Oliveri si nou venitul chitarist/clape Dave Catching. Originile proiectului dateaza din 1995, atunci cand Homme, simtind sfarsitul iminent al trupei Kyuss, a decis sa se mute la Seattle pentru a canta alaturi de The Screaming Trees.
La scurt timp dupa aceasta, el a inceput sa lucreze alaturi de muzicieni precum Van Conner (Screaming Trees), Matt Cameron (Soundgarden) si Mike Johnson (Dinosaur Jr.) si a lansat primul EP sub numele Gamma Ray. Dupa redenumirea trupei in Queens of the Stone Age, Homme l-a recrutat pe Hernandez pentru a incepe lucrul la albumul lor de debut autointitulat.
In 2000, trupa lanseaza cel de-al doilea album, "R", dupa care trupa porneste in turneul Ozzfest. Trupa primeste o multime de critici favorabile pentru concertele sustinute de ei, iar in 2001 acestia concerteaza la Rock in Rio (dupa care Oliveri a fost arestat de politia braziliana pentru ca a aparut gol pe scena).
Fostul baterist al trupei Nirvana, Dave Grohl, se alatura trupei pentru inregistrarile la cel de-al treilea album si pentru turneul de promovare ce a urmat. Unul dintre cele mai asteptate albume ale anului 2002, "Songs for the Deaf", apare in 2002 si devine un hit instantaneu, mai ales datorita single-urilor "No One Knows" si "Go With The Flow". Homme se alatura, intre timp, vechiului lui prieten, Jesse Hughes, pentru a forma proiectul Eagles of Death Metal, trupa alaturi de care lanseaza LP-ul "Peace Love Death Metal" in 2004.
La realizarea albumului "Lullabies to Paralyze", lansat in 2005, membrii trupei erau Homme, Joey Castillo, Alain Johannes, Van Leeuwan si Lanegan. In 2007 trupa lanseaza excelentul "Era Vulgaris", album la care a contribuit si Julian Casablancas de la The Strokes. Single-urile "Make it Wit Chu", "Sick, Sick, Sick" si "3's & 7's" au devenit rapid hituri pe radiourile de profil.
Artist
