В 2001 году участники QOTSA выступили на фестивале Rock In Rio проходившим в Рио-де-Жанейро, где басист группы Ник Оливери был задержан бразильской полицией за выступление в обнаженном виде. Вслед за этим, группа вновь выступила на престижном фестивале Ozzfest. Под конец тура в поддержку Rated R, группа выступила на фестивале Rock am Ring в Германии: это, по словам Джоша, «было самое ужасное шоу из тех, что мы года-либо играли, и это перед 40,000 людей». А после этого группа сделала себе тату; Оливери:

В том же году, Джош Омм и Ник Оливери приступили к записи очередной части серии The Desert Sessions и вслед за этим, приступили к записи очередной пластинки QOTSA.

Songs for the Deaf (2001—2004)

Для записи альбома 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.

Lullabies to Paralyze (2004—2006)

В конце 2004 года Омм (вокал, ударные, гитара, фортепиано, бас, перкуссия), ван Льювен (бас, гитара, вокал, клавишные) и Джои Кастильо (ударные, перкуссия) совместно с Алланом Джохеннесом (бас, гитара, флейта, саксофон) из Eleven приступили к записи четвёртого альбома группы Lullabies to Paralyze, название которого было взято из песни «Mosquito Song» из предыдущего альбома. Также в записи участвовали несколько приглашённых гостей: Ширли Мэнсон из Garbage, Бродли Далл и Билли Гиббонс из ZZ Top. Как сообщается, Ланеган отклонил приглашение остаться в группе, записал вокальные партии некоторых новых песен, и участвовал в туре как и планировалось по состоянию здоровья. Ходили слухи, будто Омм уволил Ланегана, но так или иначе, они были опровергнуты Оммом в 2005 году: