NEDD8 is a novel ubiquitin-like protein that has been shown to conjugate to nuclear proteins in a manner analogous to ubiquitination and sentrinization. To identify proteins that are involved in the NEDD8-conjugation and de-conjugation pathway, the yeast two-hybrid system was used to screen a human heart cDNA library using NEDD8 as a bait. Seven strongly positive clones were found to contain a cDNA insert encoding the ubiquitin C-terminal hydrolase, UCH-L3. In vitro GST pull-down assay demonstrated that UCH-L3 bound to both NEDD8 and ubiquitin. In contrast, UCH-L3 did not bind to sentrin-1, sentrin-2, or sentrin-3. Recombinant UCH-L3, but not UCH-L1, was able to cleave the C-terminus of NEDD8. Thus, UCH-L3 can function as a C-terminal hydrolase for both NEDD8 and ubiquitin. UCH-L3 may play a physiologically significant role in the cleavage of the C-terminus of NEDD8, which is required for NEDD8 to conjugate to target proteins.