USP9X is a conserved deubiquitinase (DUB) that regulates multiple cellular processes. Dysregulation of USP9X has been linked to cancers and X-linked intellectual disability. Here, we report the crystal structure of the USP9X catalytic domain at 2.5-Å resolution. The structure reveals a canonical USP-fold comprised of fingers, palm, and thumb subdomains, as well as an unusual β-hairpin insertion. The catalytic triad of USP9X is aligned in an active configuration. USP9X is exclusively active against ubiquitin (Ub) but not Ub-like modifiers. Cleavage assays with di-, tri-, and tetraUb chains show that the USP9X catalytic domain has a clear preference for K11-, followed by K63-, K48-, and K6-linked polyUb chains. Using a set of activity-based diUb and triUb probes (ABPs), we demonstrate that the USP9X catalytic domain has an exo-cleavage preference for K48- and endo-cleavage preference for K11-linked polyUb chains. The structure model and biochemical data suggest that the USP9X catalytic domain harbors three Ub binding sites, and a zinc finger in the fingers subdomain and the β-hairpin insertion both play important roles in polyUb chain processing and linkage specificity. Furthermore, unexpected labeling of a secondary, noncatalytic cysteine located on a blocking loop adjacent to the catalytic site by K11-diUb ABP implicates a previously unreported mechanism of polyUb chain recognition. The structural features of USP9X revealed in our study are critical for understanding its DUB activity. The new Ub-based ABPs form a set of valuable tools to understand polyUb chain processing by the cysteine protease class of DUBs.