Группа Queens Of The Stone Age была сформирована на пепелище команды Kyuss, распавшейся в 1995 году. Бывший её участник, вокалист и гитарист Джош Омм отправился в Сиэтл, чтобы принять участие в туре команды Screaming Trees, и вскоре собрал новую группу: Ван Коннер (Screaming Trees), Мэтт Кэмерон (Soundgarden и Pearl Jam) и Майк Джонсон (Dinosaur Jr.).
Музыканты выпустили одноимённый мини-альбом под вывеской Gamma Ray, состоящий из двух песен: «Born to Hula» и «If Only Everything». Но после того, как в 1997 году одноименная пауэр-метал-группа пригрозила засудить Джоша, название было изменено на Queens of the Stone Age.
Первым официальным релизом после смены названия на Queens Of The Stone Age был мини-альбом Kyuss/Queens of the Stone Age, включавший с себя материал, записанный незадолго до распада Kyuss, и некоторые записи Gamma Ray.
Джош Омм пригласил для записи дебютной пластинки бывшего коллегу по Kyuss барабанщика Альфредо Эрнандеса, а сам исполнял гитарные и басовые партии. Лидер группы хотел, чтобы его коллега из Screaming Trees Марк Ланеган тоже принял участие в записи, но тот не смог в силу обстоятельств. Одноименный дебют был выпущен в 1998 году через лейбл Loosegroove (а также на виниле через Man's Ruin). После того, как материал альбома был готов, в состав Queens Of The Stone Age влился ещё один бывший участник Kyuss басист Ник Оливери, и вскоре состав группы был укомплектован клавишником Дейвом Кэтчингом. После нескольких гастрольных туров, лидер группы Джош Хомми потрудился над серией альбомов The Desert Sessions для инди-лейбла Man's Ruin, совместно с музыкантами из Soundgarden, Fu Manchu, Monster Magnet и др.
В середине 2000 года QOTSA выпустили очередной лонгплей под лаконичным названием Rated R, в записи которого кто только ни участвовал: барабанщики Ник Ласеро и Йен Траутман, гитаристы Дэйв Кэчинг и Брэндон МакНиколь, Крис Госс, Марк Ланеган (который с этих пор и до 2005 числился в составе группы) и даже фронтмен Judas Priest Роб Хелфорд, который появился на «Feel Good Hit of the Summer». Альбом получил множество позитивных отзывов и привлёк больше внимания, чем их дебют. Успех записи свёл группу с The Smashing Pumpkins, Foo Fighters, Hole, и Queens Of The Stone Age выступили на ежегодном фестивале Ozzfest. Выступления команды сопровождали барабанщики Йен Траутман и Ники Ласеро. Масштабную известность QOTSA принесли в большей мере эффектные выступления, отчеты о которых появлялись в различных средствах музыкальной информации включая престижный музыкальный журнал Rolling Stone.
В 2001 году участники QOTSA выступили на фестивале Rock In Rio, проходившем в Рио-де-Жанейро, где басист группы Ник Оливери был задержан бразильской полицией за выступление в обнаженном виде. Вслед за этим группа вновь выступила на престижном фестивале Ozzfest. Под конец тура в поддержку Rated R группа выступила на фестивале Rock am Ring в Германии: это, по словам Джоша, «было самое ужасное шоу из тех, что мы года-либо играли, и это перед 40 000 людей».
В том же году Джош Омм и Ник Оливери приступили к записи очередной части серии The Desert Sessions и вслед за этим приступили к записи очередной пластинки QOTSA.
Для записи альбома Songs For The Deaf был приглашен знаменитый ударник Nirvana и вокалист Foo Fighters Дэйв Грол. На удивление многим, Дэйв Грол принял приглашение от QOTSA на запись альбома и сопровождение группы в их гастрольном туре, несмотря на то, что у Foo Fighters уже был готов к выпуску новый альбом. Позднее, Джош Омм и Ник Оливери приступили к работе над саундтреком к киноленте The Dangerous Lives Of Altar Boys совместно с барабанщиком Брэдом Уилком из Rage Against The Machine. Вслед за этим, музыканты сформировали новый проект Headband, вместе с басистом Твигги Рамиресом, который выступал в группе Мэрилина Мэнсона, и вокалистом Кэйси Кеосом из Amen.
Будучи одним из самых ожидаемых рок альбомов года, Songs For The Deaf был выпущен в августе 2002 года, в поддержку которого команда совершила тур с приглашенными музыкантами: Дэйвом Гролом (коего позже заменил Джои Кастильо), Марком Ленеганом (который участвовал непосредственно в записи) и Троем Ван Левеном из A Perfect Circle (последний числится в группе до сих пор). Кульминацией тура стали выступления QOTSA в роли хэдлайнеров в Австралии в январе 2004. После года гастролирования, Ник Оливери был уволен Оммом по причине чрезмерных вечеринок и неуважения к поклонникам группы. Джош обосновал данный поступок в 2005-м году тем, что он получил доказательства, что Ник жестоко обращался со своей подругой. Джош прояснил на радио BBC: «Несколько лет назад я поговорил с Ником о слухах, что я слышал. Я сказал: „Если я узнаю, что это правда, то я тебя знать не хочу“». В прессе Ник возразил, заявив что «был вытравлен жаждущим власти», и что группа без него была «Queens Lite»; позже Ник смягчил своё мнение, сказав: «У меня с Джошем хорошие отношения. Новая запись Квинзов надрала зад». К концу года, Джош и Ник все же пожали друг другу руки, но последний так и не принимал участия в записи новой пластинки, так как материал был уже готов.
За несколько месяцев альбом стал очень популярным в мире. «No One Knows» — стал первым суперхитовым синглом, а за ним последовал «Go With the Flow», который также стал очень успешным на радио и MTV. Обе песни позже появились в видео играх Guitar Hero и Rock Band.
В конце 2004 года Омм (вокал, ударные, гитара, фортепиано, бас, перкуссия), ван Льювен (бас, гитара, вокал, клавишные) и Джои Кастильо (ударные, перкуссия) совместно с Алланом Джохеннесом (бас, гитара, флейта, саксофон) из Eleven приступили к записи четвёртого альбома группы Lullabies to Paralyze, название которого было взято из песни «Mosquito Song» из предыдущего альбома. Также в записи участвовали несколько приглашённых гостей: Ширли Мэнсон из Garbage, Бродли Далл и Билли Гиббонс из ZZ Top. Как сообщается, Ланеган отклонил приглашение остаться в группе, записал вокальные партии некоторых новых песен, и участвовал в туре как и планировалось по состоянию здоровья. Ходили слухи, будто Омм уволил Ланегана, но так или иначе, они были опровергнуты Оммом в 2005 году.
Lullabies to Paralyze просочился в интернет в феврале 2005 и 3 марта появился в эфире Triple J. Официальный релиз пластинки состоялся в 22 марта 2005 года через лейбл Interscope Records. Альбом дебютировал в Billboard Music Chart под номером 5, что на данный момент является наилучшим достижением группы. Песня «In My Head» с нового альбома попала в саундтрек к игре Need for Speed: Underground 2.
14 мая 2005 Queens Of The Stone Age стали музыкальным гостем на Saturday Night Live, где их первой песней стала «Little Sister». 22 ноября группа выпустила концертник Over the Years and Through the Woods, бонусом к которому были старые видео с 1998 по 2005 год. Осенью 2005 года QotSA выступали с Nine Inch Nails в туре в поддержку нового альбома последних; в первой части тура их сопровождали Autolux, а во второй — Death From Above 1979. 19 и 20 декабря гитарист NIN появлялся на сцене с Queens Of The Stone Age, исполняя песни «Born to Hula», «Regular John», «Avon», «Monsters in the Parasol» и «Long, Slow Goodbye». Другим интересным событием 20 числа стало появление на одной сцене с QotSA Джона Гарсии, бывшего вокалиста Kyuss: подобного не совершалось ещё с 1997 года. Вместе они исполнили песни времён Kyuss: «Thumb», «Hurricane» и «Supa Scoopa and Mighty Scoop».
В день св. Валентина в 2007 году на официальном сайте группы было объявлено, что новый альбом под названием Era Vulgaris выйдет в июне. Некоторые сайты сообщали, что на записи будет присутствовать много гостей, включая Трэнта Резнора из Nine Inch Nails, Юлиана Касабланкаса из The Strokes, Марка Ланегана, Билли Гибонса из ZZ Top и покойного юмориста Эрма Бомбека. Предполагалось, что в записи также будет участвовать басист Death From Above 1979, но он на записи так и не появился. Запись Era Vulgaris завершилась в начале апреля 2007 года, а сам альбом вышел 12 июня. Омм описал альбом как «тёмный, тяжёлый и электрический, типа как строитель». Когда фронтмена спросили о его вокале на записи, он ответил: «Я хотел попробовать фигню, которая на первый взгляд казалась совершенно неловкой».
Во время тура басист Майкл Шумен (Wires on Fire, Jubilee, Mini Mansions) и клавишник Дин Фертита (Hello=Fire, The Waxwings, The Dead Weather) заменили Аллана Джохеннеса и Натали Шнейдер соответственно. В июле того же года Трой Ван Левен объявил, что группа написала новый материал, «пока что в зачаточном состоянии»; позже Омм предположил, что он будет выпущен как мини-альбом. В интервью с Джошем The Globe and Mail сообщали, что EP «может будет состоять примерно из 10 B-сайдов, записанных во время сессии Era Vulgaris». Позже было сообщено, что мини-альбом не будет выпущен, так как лейбл сейчас не желает его выпускать.
Группа начала свой североамериканский тур под названием «Duluth Tour», так как QotSA собирались посетить многие маленькие города, в которых они не были ранее, в том числе Дулус. Коллектив посетил многие другие места, например Соединённое Королевство, где на этот раз он отыграл больше концертов, чем когда-либо. В конце марта — начале апреля группа гастролировала по Австралии, а после этого завершила свой тур в Канаде в 2008 году.
В связи со смертью Наташи Шнайдер 2 июля 2008 года официальный сайт Queens Of The Stone Age был обновлён мемориальным сообщением Омма. 16 августа в Лос-Анджелесе был проведён концерт в память об умершей клавишнице. На сцене появились Аллан Джохеннес, Джек Блэк, Кайл Гесс, Мэтт Кэмерон, Броди Даль, Джесси Хьюз, Крис Госс и Пи Джей Харви. Выручка от концерта пошла на покрытие расходов, связанных с болезнью Наташи Шнайдер.
Во время последнего концерта на Reading and Leeds Festivals Омм объявил, что собирается вернуться в студию, чтобы начать работу над новым альбомом.
На протяжении 2009—2010 годов участники группы занимались другими проектами. Трой основал новую группу Sweethead, Кастильо барабанил в Eagles of Death Metal в их туре в поддержку альбома Heart On, Шуман стал новым барабанщиком и вокалистом в Mini Mansions, Фертита — гитаристом и клавишником в The Dead Weather, а Омм стал гитаристом в новой группе Them Crooked Vultures. 3 августа 2010 группа выпустила два CD делюкс издания Rated R.
В 2011 году QotSA выступили на Австралийском фестивале Soundwave, 26 июня они появились в Саммерсэте на Glastonbury Festival, а 3 и 4 сентября отыграли на 20 фестивале Pearl Jam Anniversary Festival.
Планы касательно нового альбома строились ещё с 2008 года, но о записи нечего не было слышно аж до тех пор, пока в ноябре 2011 года частый гость группы Аллан Джохеннес не рассказал следующее: «Мы с Квинзами опять сидели допоздна. Как-то мы начали процесс, он подходит к завершению. Так что я не могу точно сказать когда, но это действительно хорошее начало.». 20 августа 2012 года на странице группы на Facebook был опубликован статус сообщающий, что они «записывали» свой новый альбом. В сентябре выяснилось, что Джош Омм и продюсер Дэйв Сарди записали песню «Nobody To Love» к фильму End of Watch. В ноябре 2012 Джош Омм сообщил об уходе барабанщика Джои Кастильо, отметив, что для нового альбома барабанные партии исполнит Дэйв Грол, который также участвовал в записи альбома Songs For The Deaf. В итоге на лонгплее появились плоды труда трёх барабанщиков: Джои, Грола и Джона Теодора. Также в записи альбома принимали участие: Ник Оливери, Аллан Джохеннес, Марк Ланеган, Трент Резнор, Джейк Ширз, Броди Даль, Элтон Джон, Алекс Тёрнер, Джеймс Лавель.
Омм также подтвердил, что новый альбом Queens of the Stone Age выйдет до их концерта на Download Festival в июне 2013. В марте 2013 стало известно, что новый альбом ... Like Clockwork, записанный на студии Омма Pink Duck Studio, выйдет в июне через лейбл Matador Records.
30 марта на фестивале Lollapalooza в Бразилии Queens of the Stone Age сыграли свою новую песню «My God Is The Sun». Там же дебютировал их новый барабанщик Джон Теодор. В начале апреля на официальном сайте группы была размещена альбомная версия «My God Is The Sun» и был опубликован трек-лист нового лонгплея. С 6 по 17 мая на сайте likeclockwork.tv публиковались видеоролики на отрывки некоторых песен из нового альбома, связанные между собой, в которых представлены четыре безымянных героя.
