Josh Homme gründete die Band 1997, zu deren Gründungsmitgliedern die ehemaligen Kyussmitglieder Alfredo Hernandez und Nick Olivieri zählten, welche dort jedoch nie zum gleichen Zeitpunkt spielten. Zwei Jahre zuvor löste sich Kyuss auf und entließ seine Mitglieder eine Vielzahl neuer Bands. In der Zwischenzeit spielte Homme aushilfsweise bei diversen Bands wie den Screaming Trees (der ehemaligen Band Mark Lanegans, siehe unten) oder Soundgarden. Ebenfalls in dieser Zeit reifen die ersten Pläne zur Verwirklichung der sog. ‚Desert Sessions’, einer stets wechselnden Gruppe befreundeter Musiker um Josh Homme, welche in mehr oder minder regelmäßigen Abständen in der Wüste Kaliforniens zusammenkommen, Musik machen und diese dann in je 2 Volumes veröffentlichen. (Inzwischen existieren zehn bzw. 5×2 Veröffentlichungen auf Vinyl und CD).
1996, vor der offiziellen Bandgründung, veröffentlicht Homme dann unter dem Namen ‚Gamma Ray’ eine 2-Track EP. Relativ schnell meldet sich jedoch ein europäischer Namensvetter und Homme muss sich nach einem neuen Bandnamen umsehen. Geistiger Vater ist auch hier einmal mehr Produzent Chris Goss, welcher sich während der Aufnahmen zu Kyuss’ ‚Blues for the Red Sun’ angeblich zu einem ‚Oh man, you guys really sound like the queens of the stone age’ hinreißen ließ.
Bevor 1998 dann das Debütalbum erscheint, werden noch zwei Split-EPs mit Kyuss bzw. Beaver veröffentlicht, welche insgesamt 5 QOTSA-Songs bieten. Auf dem nach der Band benannten 1. Album spielen dann jedoch nur Josh Homme (Gitarre und unter dem Synonym ‚Carlo von Sexron’ Bass) sowie Alfredo Hernandez, da Olivieri zu der Zeit mit den Aufnahmen zu ‚Cocaine Rodeo’ seiner Band ‚Mondo Generator’ beschäftigt ist. Auf der anschließenden, 2-jährigen Tour (u.a. mit Bands wie Ween, Hole, Rage Against The Machine und Bad Religion) ist er aber mit an Board, ebenso wie Dave Catching.
Musikalisch distanziert sich Homme stark von Kyuss, die Songs wirken nicht mehr so schwer, was nicht zuletzt an der im Vergleich zu John Garcias Stimme bei Kyuss fragilen Gesangsweise Hommes und dem recht minimalistischen Drumming liegt.
Vor den Aufnahmen zum zweiten Album ‚Rated R’ verlässt Alfredo Hernandez die Band und wird von Gene Troutman ersetzt. Das QOTSA-Musiker-Karussel nimmt Fahrt auf, zentrale Mitglieder bleiben aber zunächst Josh Homme und Nick Olivieri. Neben den o.g. bereichern eine Vielzahl anderer Musiker das Album, darunter Mark Lanegan (singt ‚In The Fade’), Rob Halford (Backingvocals auf ‚Feel Good Hit Of The Summer’), Chris Goss, Pete Stahl & Nick Lucero. Die Tour zum Album bestreitet die Band mit Monster Magnet und stellt 2001 Mark Lanegan als neues, festes Bandmitglied vor. Inzwischen ebenfalls fester Bestandteil der Band ist Troy Van Leeuwen (A Perfect Circle u.a. ) Mitte desselben Jahres beginnen auch die Arbeiten an ‚Songs For The Deaf’, dem endgültigen Durchbruchsalbum der Band. Nicht ganz unschuldig daran dürfte der Umstand sein, dass sich mit Dave Grohl ein prominenter Fan der Band hinter die Felle gesetzt und das gesamte Album eingetrommelt hat. Da dies aber (bis auf einige wenige Promoauftritte im Anschluss an die Veröffentlichung) eine einmalige Angelegenheit bleibt, wird der Ex-Danzig Drummer Joey Castillo an Board geholt.
Im Februar 2004 wird die Bandkonstellation dann erneut ordentlich durch den Reißwolf gedreht. Nach bandinternen Querelen wird außerdem Nick Olivieri aus der Band geschmissen. Anscheinend waren die Eskapaden Olivieris ausschlaggebend für Hommes Entscheidung, ihn aus der Band zu werfen. Endgültig geklärt und nachvollziehbar gemacht werden die Gründe allerdings nicht, seitens der Plattenfirma Interscope hieß es lediglich, die beiden seien “in den letzten 18 Monaten so häufig aneinander geraten, dass eine fruchtbare Zusammenarbeit innerhalb der Band nicht länger gewährleistet ist”.
Auf dem anno 2005 erscheinenden, vierten Album der Band ‚Lullabies To Paralyze’ ist demnach nur noch ein Gründungsmitglied der Band zu hören. Alles beim Alten also, was die Mitgliederrotation betrifft. Und auch diesmal konnten für das Album namhafte Gastmusiker erfolgreich ins Studio eingeladen werden. So trugen z.B. Billy Gibbons (ZZ Top), Brody Dalle (Distillers), Shirley Manson (Garbage) und Alain Johannes sowie Natasha Shneider (beide Eleven). Letztere ergänzen auch das Live Line-Up, bestehend aus Josh Homme, Troy Van Leeuwen, Joey Castillo und den bei oben genannten.