Small ubiquitin-related modifier (SUMO) proteins are conjugated to numerous polypeptides in cells, and attachment of SUMO plays important roles in regulating the activity, stability, and subcellular localization of modified proteins. SUMO modification of proteins is a dynamic and reversible process. A family of SUMO-specific proteases catalyzes the deconjugation of SUMO-modified proteins. Members of the Sentrin (also known as SUMO)-specific protease (SENP) family have been characterized with unique subcellular localizations. However, little is known about the functional significance of or the regulatory mechanism derived from the specific localizations of the SENPs. Here we identify a bipartite nuclear localization signal (NLS) and a CRM1-dependent nuclear export signal (NES) in the SUMO protease SENP2. Both the NLS and the NES are located in the nonhomologous domains of SENP2 and are not conserved among other members of the SENP family. Using a series of SENP2 mutants and a heterokaryon assay, we demonstrate that SENP2 shuttles between the nucleus and the cytoplasm and that the shuttling is blocked by mutations in the NES or by treating cells with leptomycin B. We show that SENP2 can be polyubiquitinated in vivo and degraded through proteolysis. Restricting SENP2 in the nucleus by mutations in the NES impairs its polyubiquitination, whereas a cytoplasm-localized SENP2 made by introducing mutations in the NLS can be efficiently polyubiquitinated, suggesting that SENP2 is ubiquitinated in the cytoplasm. Finally, treating cells with MG132 leads to accumulation of polyubiquitinated SENP2, indicating that SENP2 is degraded through the 26S proteolysis pathway. Thus, the function of SENP2 is regulated by both nucleocytoplasmic shuttling and polyubiquitin-mediated degradation.