Addition and removal of ubiquitin or ubiquitin chains to and from proteins is a tightly regulated process that contributes to cellular signaling and protein stability. Here we show that phosphorylation of the human deubiquitinase DUBA (OTUD5) at a single residue, Ser177, is both necessary and sufficient to activate the enzyme. The crystal structure of the ubiquitin aldehyde adduct of active DUBA reveals a marked cooperation between phosphorylation and substrate binding. An intricate web of interactions involving the phosphate and the C-terminal tail of ubiquitin cause DUBA to fold around its substrate, revealing why phosphorylation is essential for deubiquitinase activity. Phosphoactivation of DUBA represents an unprecedented mode of protease regulation and a clear link between two major cellular signal transduction systems: phosphorylation and ubiquitin modification.