Oliveri was a core contributor to Queens of the Stone Age from 1998 to 2004, playing bass and providing backup and lead vocals on two of the band's biggest albums, "Rated R" and "Songs for the Deaf," in addition to co-writing most of the album's songs with bandmate Josh Homme. He first appeared on the band's self titled debut album in the form of a voicemail confirming his commitment to the band on the album's final song, "I Was a Teenage Hand Model".