The mechanisms that regulate the nucleocytoplasmic localization of human deubiquitinases remain largely unknown. The nuclear export receptor CRM1 binds to specific amino acid motifs termed NESs (nuclear export sequences). By using in silico prediction and experimental validation of candidate sequences, we identified 32 active NESs and 78 inactive NES-like motifs in human deubiquitinases. These results allowed us to evaluate the performance of three programs widely used for NES prediction, and to add novel information to the recently redefined NES consensus. The novel NESs identified in the present study reveal a subset of 22 deubiquitinases bearing motifs that might mediate their binding to CRM1. We tested the effect of the CRM1 inhibitor LMB (leptomycin B) on the localization of YFP (yellow fluorescent protein)- or GFP (green fluorescent protein)-tagged versions of six NES-bearing deubiquitinases [USP (ubiquitin-specific peptidase) 1, USP3, USP7, USP21, CYLD (cylindromatosis) and OTUD7B (OTU-domain-containing 7B)]. YFP–USP21 and, to a lesser extent, GFP–OTUD7B relocated from the cytoplasm to the nucleus in the presence of LMB, revealing their nucleocytoplasmic shuttling capability. Two sequence motifs in USP21 had been identified during our survey as active NESs in the export assay. Using site-directed mutagenesis, we show that one of these motifs mediates USP21 nuclear export, whereas the second motif is not functional in the context of full-length USP21.