The 26S proteasome mediates degradation of ubiquitin-conjugated proteins. Although ubiquitin is recycled from proteasome substrates, the molecular basis of deubiquitination at the proteasome and its relation to substrate degradation remain unknown. The Rpn11 subunit of the proteasome lid subcomplex contains a highly conserved Jab1/MPN domain-associated metalloisopeptidase (JAMM) motif-EX(n)HXHX(10)D. Mutation of the predicted active-site histidines to alanine (rpn11AXA) was lethal and stabilized ubiquitin pathway substrates in yeast. Rpn11(AXA) mutant proteasomes assembled normally but failed to either deubiquitinate or degrade ubiquitinated Sic1 in vitro. Our findings reveal an unexpected coupling between substrate deubiquitination and degradation and suggest a unifying rationale for the presence of the lid in eukaryotic proteasomes.