Uch37 is one of the three principal deubiquitinating enzymes (DUBs), and the only ubiquitin carboxy-terminal hydrolase (UCH)-family protease, that is associated with mammalian proteasomes. We show that Uch37 is responsible for the ubiquitin isopeptidase activity in the PA700 (19S) proteasome regulatory complex. PA700 isopeptidase disassembles Lys 48-linked polyubiquitin specifically from the distal end of the chain, a property that may be used to clear poorly ubiquitinated or unproductively bound substrates from the proteasome. To better understand Uch37 function and the mechanism responsible for its specificity, we investigated how Uch37 is recruited to proteasomes. Uch37 binds through Adrm1, a previously unrecognized orthologue of Saccharomyces cerevisiae Rpn13p, which in turn is bound to the S1 (also known as Rpn2) subunit of the 19S complex. Adrm1 (human Rpn13, hRpn13) binds the carboxy-terminal tail of Uch37, a region that is distinct from the UCH catalytic domain, which we show inhibits Uch37 activity. Following binding, Adrm1 relieves Uch37 autoinhibition, accelerating the hydrolysis of ubiquitin-7-amido-4-methylcoumarin (ubiquitin-AMC). However, neither Uch37 alone nor the Uch37-Adrm1 or Uch37-Adrm1-S1 complexes can hydrolyse di-ubiquitin efficiently; rather, incorporation into the 19S complex is required to enable processing of polyubiquitin chains.