Nese ano a banda colaboru co artista Lust para o álbum Pigs of the Roman Empire, e co vocalista de Dead Kennedys Jello Biafra para Never Breathe What You Can't See e Sieg Howdy!, editados nos anos 2004 e 2005 respectivamente. Never Breathe What You Can't See estivo promocionado por unha pequena xira con Jello Biafra e Adam Jones de Tool. Planeouse unha xira europea pero foi cancelada no mes de outubro do 2004 debido a problemas con Rutmanis. Melvins rematou o ano facendo un feixe de concertos con David Scott Stone promocionando o traballo do director de cine Cameron Jamie en Europa e nos Estados Unidos.