É uma banda americana de Rock Alternativo. Após a separação de sua banda anterior, a Kyuss, em 1995, Josh Homme se juntou brevemente a banda Screaming Trees como guitarrista de turnê, antes de decidir formar uma nova banda, a Gamma Ray. O seu EP, Gamma Ray, foi lançado em 1996. A Gamma Ray mudou seu nome em 1997 depois que a banda alemã Gamma Ray de Power Metal ameaçou processá-la. O nome Queens of the Stone Age veio de um apelido dado a Kyuss por seu produtor Chris Goss. O primeiro lançamento sob o nome Queens of the Stone Age foi a música "18 AD", lançada no álbum de compilação, Burn One Up! Music for Stoners, da Roadrunner Records. A primeira apresentação ao vivo da banda foi em 20 de novembro de 1997, no OK Hotel em Seattle. O seu primeiro álbum, Queens of the Stone Age, foi lançado em 22 de setembro de 1998 pela Loosegroove Records. Homme tocou guitarra e baixo no álbum, Alfredo Hernández na bateria e várias outras contribuições de Chris Goss e Hutch. Logo após o término das gravações, o baixista Nick Oliveri se juntou a banda, e a turnê começou com uma banda composta inteiramente por ex-membros da Kyuss. A formação da banda mudaria com frequência. O seu segundo álbum, Rated R, foi lançado em 6 de junho de 2000 pela Interscope Records, com vários músicos participando da gravação.
Durante o show do Rock in Rio de 2001 no Brasil, o baixista Nick Oliveri foi preso após se apresentar nu no palco, com apenas seu baixo cobrindo seus genitais. Mark Lanegan se juntou à banda como membro em tempo integral nos teclados. O seu terceiro álbum, Songs for the Deaf, foi lançado em agosto de 2002, com a participação de Dave Grohl, vocalista do Foo Fighters na bateria. A canção "No One Knows" foi o primeiro single do álbum, e foi o primeiro single da banda a entrar na Billboard Hot 100 na posição 51, e seu único single a chegar ao topo na Billboard Alternative Airplay. A canção também recebeu uma indicação para Melhor Performance de Hard Rock no Grammy Awards de 2003. A sua Songs for the Deaf Tour teve uma série de datas na Austrália em janeiro de 2004. Grohl retornou aos seus outros projetos e foi substituído na parte europeia da turnê pelo baterista Joey Castillo, que se juntou à banda em tempo integral. Após a turnê, Homme demitiu Oliveri. O seu quarto álbum, Lullabies to Paralyze, foi lançado em 22 de março de 2005, estreando na quinta posição na Billboard 200. Lanegan saiu da banda e foi substituído por Natasha Shneider. O seu primeiro álbum ao vivo, Over the Years and Through the Woods, foi lançado em 22 de novembro de 2005 em formato de DVD. O seu quinto álbum, Era Vulgaris, foi lançado em 20 de julho de 2007 no Reino Unido e 21 de julho nos EUA, e 29 de julho em outros países. O álbum estreou na posição 14 na Billboard 200.
Em novembro de 2007, a banda fez um set semiacústico em uma mina de sal subterrânea na Alemanha. Em 2 de julho de 2008, a ex-tecladista da banda, Natasha Shneider, faleceu de câncer de pulmão aos 52 anos. Em 2010, Homme sofreu complicações durante uma cirurgia malfeita no joelho, e ficou acamado por 4 meses, e mergulhou em uma depressão profunda, durante a qual considerou desistir de sua carreira musical. Após a recuperação de Homme, a banda lançou uma versão remasterizada do seu primeiro álbum no início de 2011 e apresentou o álbum na íntegra em uma turnê promocional. Em novembro de 2012, Homme informou que Joey Castillo havia deixado a banda. O seu sexto álbum, ...Like Clockwork, foi lançado em junho de 2013 pela Matador Records, com contribuição de Grohl, de Castillo e do novo baterista Jon Theodore. O álbum estreou no topo na Billboard 200, e foi o primeiro álbum da banda a atingir essa classificação. A banda estreou a canção "My God Is The Sun", no Lollapalooza Brasil em 30 de março de 2013, e com a estréia ao vivo de Theodore. A banda se apresentou no Festival Rock in Rio, no Brasil, em setembro de 2015. O seu sétimo álbum Villains, foi lançado em 25 de agosto de 2017. Em 24 de outubro de 2017, durante a sua Villains Tour, a banda foi a atração principal pela primeira vez do Madison Square Garden, em Nova York. O ex-tecladista Mark Lanegan faleceu em 2022. O seu oitavo álbum, In Times New Roman..., foi lançado em 16 de junho de 2023.