von Hippel-Lindau (VHL) disease is a hereditary cancer syndrome caused by germline mutations of the VHL gene. Recent studies suggest that VHL protein (pVHL) is a component of an E3 ubiquitin ligase, but the detailed biological function of pVHL remains to be determined. To further elucidate the biological functions of pVHL, we searched pVHL-interacting proteins using yeast two-hybrid screening. A novel protein named VHL-interacting deubiquitinating enzyme 1 (VDU1) was identified as being able to directly interact with pVHL in vitro and in vivo. We have determined the full-length cDNA of this enzyme, which includes two putative subtypes. Type I consists of 942 amino acids, and type II consists of 911 amino acids with predicted molecular masses of 107 and 103 kDa, respectively. We have also cloned a mouse homologue of this enzyme. Sequence analysis reveals that this protein is conserved between human and mouse and contains the signature motifs of the ubiquitin-specific processing protease family. Enzymatic function studies demonstrate its deubiquitinating activity. We have determined that the VDU1-interacting region in pVHL is located in its beta-domain, and several naturally occurring mutations located in this domain disrupt the interaction between pVHL and VDU1 protein. Co-immunoprecipitation demonstrates that VDU1 can be recruited into the pVHL-elongin C-elongin B complex. Finally, we demonstrate that VDU1 is able to be ubiquitinated via a pVHL-dependent pathway for proteasomal degradation, and VHL mutations that disrupt the interaction between VDU1 and pVHL abrogate the ubiquitination of VDU1. Our findings indicate that VDU1, a novel ubiquitin-specific processing protease, is a downstream target for ubiquitination and degradation by pVHL E3 ligase. Targeted degradation of VDU1 by pVHL could be crucial for regulating the ubiquitin-proteasome degradation pathway.