UCH37, also known as UCHL5, is a highly conserved deubiquitinating enzyme (DUB) that associates with the 26S proteasome. Recently, it was reported that UCH37 activity is stimulated by branched ubiquitin (Ub) chain architectures. To understand how UCH37 achieves its unique debranching specificity, we performed biochemical and Nuclear Magnetic Resonance (NMR) structural analyses and found that UCH37 is activated by contacts with the hydrophobic patches of both distal Ubs that emanate from a branched Ub. In addition, RPN13, which recruits UCH37 to the proteasome, further enhances branched-chain specificity by restricting linear Ub chains from having access to the UCH37 active site. In cultured human cells under conditions of proteolytic stress, we show that substrate clearance by the proteasome is promoted by both binding and deubiquitination of branched polyubiquitin by UCH37. Proteasomes containing UCH37(C88A), which is catalytically inactive, aberrantly retain polyubiquitinated species as well as the RAD23B substrate shuttle factor, suggesting a defect in recycling of the proteasome for the next round of substrate processing. These findings provide a foundation to understand how proteasome degradation of substrates modified by a unique Ub chain architecture is aided by a DUB.