Eight different types of ubiquitin linkages are present in eukaryotic cells that regulate diverse biological processes. Proteins that mediate specific assembly and disassembly of atypical Lys6, Lys27, Lys29 and Lys33 linkages are mainly unknown. We here reveal how the human ovarian tumor (OTU) domain deubiquitinase (DUB) TRABID specifically hydrolyzes both Lys29- and Lys33-linked diubiquitin. A crystal structure of the extended catalytic domain reveals an unpredicted ankyrin repeat domain that precedes an A20-like catalytic core. NMR analysis identifies the ankyrin domain as a new ubiquitin-binding fold, which we have termed AnkUBD, and DUB assays in vitro and in vivo show that this domain is crucial for TRABID efficiency and linkage specificity. Our data are consistent with AnkUBD functioning as an enzymatic S1' ubiquitin-binding site, which orients a ubiquitin chain so that Lys29 and Lys33 linkages are cleaved preferentially.