Ubiquitin-specific protease 8 (USP8) hydrolyzes mono and polyubiquitylated targets such as epidermal growth factor receptors and is involved in clathrin-mediated internalization. In 1182 residues, USP8 contains multiple domains, including coiled-coil, rhodanese, and catalytic domains. We report the first high-resolution crystal structures of these domains and discuss their implications for USP8 function. The amino-terminal domain is a homodimer with a novel fold. It is composed of two five-helix bundles, where the first helices are swapped, and carboxyl-terminal helices are extended in an antiparallel fashion. The structure of the rhodanese domain, determined in complex with the E3 ligase NRDP1, reveals the canonical rhodanese fold but with a distorted primordial active site. The USP8 recognition domain of NRDP1 has a novel protein fold that interacts with a conserved peptide loop of the rhodanese domain. A consensus sequence of this loop is found in other NRDP1 targets, suggesting a common mode of interaction. The structure of the carboxyl-terminal catalytic domain of USP8 exhibits the conserved tripartite architecture but shows unique traits. Notably, the active site, including the ubiquitin binding pocket, is in a closed conformation, incompatible with substrate binding. The presence of a zinc ribbon subdomain near the ubiquitin binding site further suggests a polyubiquitin-specific binding site and a mechanism for substrate induced conformational changes.