Queens of the Stone Age
Upphaflega var sveitin stofnuð árið 1996 undir nafninu Gamma Ray en sveitin þurfti svo að breyta um nafn ári seinna eftir að þýsk power-metal hljómsveit með sama nafn hótaði að kæra. Fyrsta plata sveitarinnar kom út árið 1998 en þar spilaði Homme bæði á gítar og bassa en vinur hans, Alfredo Hernandez spilaði á trommur. Platan hét einfaldlega Queens of the Stone Age en stuttu eftir að upptökum var lokið gengu bassaleikarinn Nick Oliveri og gítarleikarinn Dave Catching til liðs við sveitina en í lok lagsins „I was a teenage hand model“ sem er síðasta lagið á plötunni má heyra upptöku af símsvara Homme þar sem Oliveri samþykkir að byrja í sveitinni.
Rated R
Eftir fyrstu plötuna voru mannabreytingar í hljómsveitinni með reglulegu millibili og sveitin gaf svo út sína aðra breiðskífu árið 2000 en hún fékk nafnið Rated R. Hún fékk góða dóma gagnrýnenda en vinsældir hennar voru þó takmarkaðar. Sveitin fékk þó að koma fram á Ozzfest 2000 og Rock in Rio ári seinna en þar var Nick Oliveri handtekinn fyrir að koma nakinn fram á sviðinu.
Songs for the deaf
Árið 2002 kom svo út þriðja breiðskífa sveitarinnar „Songs for the deaf“ en á henni trommaði fyrrum liðsmaður Nirvana og núverandi forsprakki Foo Fighters, Dave Grohl. Einnig hafði gítarleikari A Perfect Circle, Troy Van Leeuwen gengið til liðs við sveitina auk þess sem fyrrum söngvari Screaming Trees, Mark Lanegan kom örlítið við sögu.
Þessi plata skaut QOTSA almennilega uppá stjörnuhimininn og lög eins og „No One Knows“ og „Go With The Flow“ urðu vinsæl og voru spiluð á MTV. Þrátt fyrir gríðarlega velgengni vildi Dave Grohl ekki vera áfram í sveitinni og sneri aftur til fyrri verkefna. Í hans stað kom svo tattúveraði harðnaglinn Joey Castillo sem enn gegnir slagverksskyldum sveitarinnar. Eftir farsælan feril var svo Nick Oliveri rekinn úr sveitinni snemma árs 2004 fyrir vanvirðingu við aðdáendur og óhóflega mikið partýstand. Seinna sagði Homme svo reyndar að raunverulega ástæða fyrir þessu væri sú að Oliveri hefði beitt kærustu sína líkamlegu ofbeldi.
Lullabies to Paralyze
Þremur árum seinna eða 2005 kom svo fjórða breiðskífan, Lullabies to Paralyze en þá hafði hinn fjölhæfi Alain Johannes gengið til liðs við sveitina. Platan seldist einstaklega vel og jók enn frekar á vinsældir sveitarinnar. Seinna sama ár gaf sveitin svo út live DVD/geisladisk sem heitir „Over the years and through the woods“. Á disknum eru upptökur af tvennum tónleikum sveitarinnar í London en einnig aukaefni úr ýmsum áttum frá árunum 1998-2005.
Era Vulgaris
Fimmta breiðskífan, Era Vulgaris kom svo út 12. júní 2007 en þar spilar Michael Shuman á bassa og Dean Fertita (áður í The Racounters) á hljómborð. Fyrsta smáskífan á plötunni heitir Sick, Sick, Sick og önnur heitir 3's and 7's. Auk þess koma fjölmargir heimsfrægir tónlistarmenn við sögu á plötunni eins og Trent Reznor forsprakki Nine Inch Nails og Julian Casablancas söngvari The Strokes. Á plötunni má finna lag sem áður kom út með Desert Sessions (hliðarverkefni Homme og vina hans), en það heitir „I wanna make it wit chu“. Plötunni var lekið á internetið þann 23. maí 2007.