Группа "Queens of the stone age" была основана на обломках команды, исполнявшей так называемый стоунер-рок "Kyuss". После распада последней в 1995 году Джош Хомм (вокал, гитара) перебрался в Сиэтл, где выступал в составе "Screaming Trees". В 1997-м он помирился со своим бывшим коллегой, басистом Ником Оливери, который после "Kyuss" играл в панковской банде "Dwarves". Парни стали подумывать о том, что неплохо было бы возродить совместную деятельность. Эту идею поддержал еще один их бывший соратник, барабанщик Альфредо Хернандес.   Четвертым членом команды стал гитарист Дэйв Катчинг. В 1998-м на собственные денежки "Queens of the stone age" записали свой одноименный дебютный лонгплей. Альбом пришелся по вкусу любителям старого доброго хард-рока, хотя и звучал вполне современно. Радиостанции быстренько взяли себе на вооружение композицию "If Only", а журнал "Rolling stone" зачислил "королев" в десятку лучших современных хард-энд-хэви групп.     В поддержку своей первой пластинки организовали турне, длившееся почти два года. За это время группа не только исколесила родные Штаты, но и побывала за границей, а компанию ей составляли такие коллективы как "Bad Religion", "Rage Against the Machine", "Smashing Pumpkins", "Hole" и "Ween". В студии коллектив оказался лишь в 2000 году. Сначала был записан EP "Feel Good Hits Of The Summer", куда вошли две кавер-версии "Kinks" – "Everybody's Gonna Be Happy" и "Who'll Be The Next In Line", а затем вышел и полноформатник "Rated R".   Последующие гастроли начались с участия в традиционном "Ozzfest". В этот период Хернандеса подменяли Джин Траутман и Ники Люсеро. Тем временем музыкальная пресса продолжала печатать положительные рецензии и на второй альбом группы. В 2001 году "Queens of the stone age" приняли участие в знаменитом фестивале "Rock in Rio". Видимо перегревшийся на жарком бразильском солнце Оливери вышел на сцену абсолютно голым, за что был арестован местной полицией.   Во время европейских дат того же года к "Королевам" присоединился бывший участник "Screaming trees" Марк Ланеган. Сначала он выступал с группой, как сессионщик, но затем стал постоянным членом коллектива. Когда же настала пора записывать очередной альбом, в команду напросился бывший ударник "Nirvana" и лидер "Foo fighters" Дэйв Грол, заявивший, что ему очень нравится та музыка, которую исполняют "Queens of the stone age".     И хотя он привнес небольшой гранжевый оттенок, но не смог испортить качественный хард-рок группы. "Songs for the deaf" в первую же неделю продаж оказался в лучшей двадцатке чартов "Billboard", разойдясь за это время тиражом в 50000 экземпляров. Некоторые проблемы были лишь с названием, поскольку некоторые глухие люди воспринимали его как насмешку над собой.   Последующий гастрольный график оказался не слишком плотным, поэтому Оливери и Хомм смогли выкроить себе время для создания нового проекта "Headband" с участием Твигги Рамиреза (экс-"Marilyn Manson") и Кэйси Чаоса (экс-"Amen), а также для записи саундтрека к фильму "The Dangerous Lives of Altar Boys".