A C-terminally modified ubiquitin (Ub) derivative, ubiquitin vinyl sulfone (UbVS), was synthesized as an active site-directed probe that irreversibly modifies a subset of Ub C-terminal hydrolases (UCHs) and Ub-specific processing proteases (UBPs). Specificity of UbVS for deubiquitylating enzymes (DUBs) is demonstrated not only by inhibition of [(125)I]UbVS labeling with N-ethylmaleimide and Ub aldehyde, but also by genetic analysis. [(125)I]UbVS modifies six of the 17 known and putative yeast deubiquitylating enzymes (Yuh1p, Ubp1p, Ubp2p, Ubp6p, Ubp12p and Ubp15p), as revealed by analysis of corresponding mutant strains. In mammalian cells, greater numbers of polypeptides are labeled, most of which are likely to be DUBs. Using [(125)I]UbVS as a probe, we report the association of an additional DUB with the mammalian 26S proteasome. In addition to the 37 kDa enzyme reported to be part of the 19S cap, we identified USP14, a mammalian homolog of yeast Ubp6p, as being bound to the proteasome. Remarkably, labeling of 26S-associated USP14 with [(125)I]UbVS is increased when proteasome function is impaired, suggesting functional coupling between the activities of USP14 and the proteasome.