Ubiquitination is a reversible modification that influences a broad range of physiological processes. There are approximately 90 deubiquitinases (DUBs) encoded in the human genome, of which 79 are predicted to have catalytic activity. We tagged 66 DUBs with green fluorescent protein and systematically surveyed their subcellular distribution, identifying enzymes specific to the nucleus, plasma membrane, and secretory and endocytic pathways. USP21 is unique in showing clear association with both centrosomes and microtubules. Using an in vitro assay, we show that microtubule binding is direct and identify a novel microtubule-binding motif encompassed within amino acids 59-75 of the N-terminus of USP21. Our functional studies indicate a key role for USP21 in the governance of microtubule- and centrosome-associated physiological processes: Depletion of USP21 in A549 cells compromises the reestablishment of a radial array of microtubules during recovery from cold-induced depolymerization and also reduces the probability of primary cilium formation, whereas USP21 knockdown in PC12 cells inhibits nerve growth factor-induced neurite outgrowth.