Gegründet in Palm Desert, Kalifornien, spielten Kyuss diverse Konzerte in der umliegenden Wüste, weshalb sie ihren Stil als Desert Rock bezeichneten. Kyuss gelten als Begründer des Stoner Rock, den sie mit ihrem sehr basslastigen Sound und schleppenden Grooves prägten. Ihr Album BLUES FOR THE RED SUN gilt als Geburtsstunde und Meilenstein des Genres. Aus Teilen der Band Kyuss entstand nach der Auflösung 1995 die Band Queens Of The Stone Age, die von Josh Homme gegründet wurde.
1987 fanden sich John Garcia (Gesang), Josh Homme (Gitarre), Brant Bjork (Schlagzeug) und Chris Cockrell (Bass, Gitarre), der später von Nick Oliveri ersetzt wurde, unter dem Namen „Katzenjammer“ zusammen, änderten diesen jedoch bald zu „Sons Of Kyuss“ und schließlich 1990 zu „Kyuss“. Ihre ersten Aufnahmen als Sons of Kyuss präsentierten sie vor allem auf den von Homme initiierten „Generator-Partys“ in der Wüste vor Palm Desert, die schnell an Popularität gewannen. Da ihre Musik für die damalige Zeit in keine Schublade passte, nannten sie ihren Stil auch aufgrund ihrer Wüsten-Konzerte Desert Rock.
Mit ihrem Album BLUES FOR THE RED SUN (1992) machten sich Kyuss auch außerhalb des Undergrounds einen Namen, noch heute gilt dieses Album als Geburtsstunde des Stoner Rock. Ende 1993 spielten Kyuss im Vorprogramm von Metallica in Australien und schon ein Jahr später unterschrieben sie beim Major-Label Elektra Records und veröffentlichten ihr Album WELCOME TO SKY VALLEY. Der Sound der Band war mittlerweile deutlich psychedelischer als zuvor und erfreute sich vor allem mit dem Hit ‘Demon Cleaner‘ großer Beliebtheit.
Kyuss‘ letztes Album …AND THE CIRCUS LEAVES THE TOWN (1995) konnte an den Erfolg des Vorgängers nicht anknüpfen und noch im selben Jahr gaben Kyuss ihre Auflösung bekannt. Mit Queens Of The Stone Age gründete Josh Homme eine neue Band, Sänger John Garcia war in mehreren Projekten wie Hermano weiter aktiv.
2010 fanden sich John Garcia, Nick Oliveri und Brant Bjork unter dem Namen „Kyuss Lives!“ wieder zusammen. 2012 mussten sie sich nach einem Rechtsstreit mit Josh Homme in Vista Chino umbenennen.