The modification of cellular proteins by ubiquitin (Ub) is an important event that underlies protein stability and function in eukaryotes. Protein ubiquitylation is a dynamic and reversible process; attached Ub can be removed by deubiquitylating enzymes (DUBs), a heterogeneous group of cysteine proteases that cleave proteins precisely at the Ub-protein bond. Two families of DUBs have been identified previously. Here, we describe new, highly specific Ub iso-peptidases, that have no sequence homology to known DUBs, but which belong to the OTU (ovarian tumour) superfamily of proteins. Two novel proteins were isolated from HeLa cells by affinity purification using the DUB-specific inhibitor, Ub aldehyde (Ubal). We have named these proteins otubain 1 and otubain 2, for OTU-domain Ubal-binding protein. Functional analysis of otubains shows that the OTU domain contains an active cysteine protease site.