The ubiquitin (Ub)-proteasome system includes a large family of deubiquitinating enzymes (DUBs). Many members are assigned to this enzyme class by sequence similarity but without evidence for biological activity. A panel of novel DUB-specific probes was generated by a chemical ligation method. These probes allowed identification of DUBs and associated components by tandem mass spectrometry, as well as rapid demonstration of enzymatic activity for gene products whose functions were inferred from primary structure. We identified 23 active DUBs in EL4 cells, including the tumor suppressor CYLD1. At least two DUBs tightly interact with the proteasome 19S regulatory complex. An OTU domain-containing protein, with no sequence homology to any known DUBs, was isolated. We show that this polypeptide reacts with the C terminus of Ub, thus demonstrating DUB-like enzymatic activity for this novel superfamily of proteases.