The VHL protein (pVHL) is a component of an E3 ubiquitin ligase complex which is involved in the ubiquitination and degradation of the α subunits of HIF (hypoxia-inducible factor) in the presence of oxygen. However, it is of considerable interest to identify pVHL substrates other than HIF. In our previous studies, we have shown that VDU1 (pVHL-interacting deubiquitinating enzyme-1) can be ubiquitinated for rapid degradation in a pVHL-dependent manner. In this report we show that another uncharacterized deubiquitinating enzyme, named VDU2 (pVHL-interacting deubiquitinating enzyme-2), is a substrate of pVHL. Based on human and mouse cDNA sequences, VDU1 and VDU2 are identical in approximately 59% of the amino acids with strong homology in the N-terminus and C-terminus and a weaker similarity in the middle region. VDU2 contains the signature motifs of the ubiquitin-specific processing protease family and possesses deubiquitinating activity. Like VDU1, VDU2 interacts with pVHL β-domain and these two proteins can compete with each other to bind to pVHL. Finally, we demonstrate that VDU2 can also be ubiquitinated and degraded in a pVHL-dependent manner. Based on their amino acid sequence homology and functional interaction with pVHL, VDU1 and VDU2 define a subfamily of ubiquitin specific processing proteases. Since deubiquitination, by reversing ubiquitination, has been recognized as an important regulatory step in ubiquitination-related processes, VDU1 and VDU2 could be important substrates of pVHL E3 ligase complex.