The NF-κB (nuclear factor κB) regulator A20 antagonises IKK [IκB (inhibitor of κB) kinase] activation by modulating Lys⁶³-linked polyubiquitination of cytokine-receptor-associated factors including TRAF2/6 (tumour-necrosis-factor-receptor-associated factor 2/6) and RIP1 (receptor-interacting protein 1). In the present paper we describe the crystal structure of the N-terminal OTU (ovarian tumour) deubiquitinase domain of A20, which differs from other deubiquitinases but shares the minimal catalytic core with otubain-2. Analysis of conserved surface regions allows prediction of ubiquitin-binding sites for the proximal and distal ubiquitin molecules. Structural and biochemical analysis suggests a novel architecture of the catalytic triad, which might be present in a subset of OTU domains including Cezanne and TRABID (TRAF-binding domain). Biochemical analysis shows a preference of the isolated A20 OTU domain for Lys⁴⁸-linked tetraubiquitin in vitro suggesting that additional specificity factors might be required for the physiological function of A20 in cells.