Herpesvirus-associated ubiquitin-specific protease (HAUSP, also known as USP7), a deubiquitylating enzyme of the ubiquitin-specific processing protease family, specifically deubiquitylates both p53 and MDM2, hence playing an important yet enigmatic role in the p53–MDM2 pathway. Here we demonstrate that both p53 and MDM2 specifically recognize the N-terminal tumor necrosis factor–receptor associated factor (TRAF)–like domain of HAUSP in a mutually exclusive manner. HAUSP preferentially forms a stable HAUSP–MDM2 complex even in the presence of excess p53. The HAUSP-binding elements were mapped to a peptide fragment in the carboxy-terminus of p53 and to a short-peptide region preceding the acidic domain of MDM2. The crystal structures of the HAUSP TRAF-like domain in complex with p53 and MDM2 peptides, determined at 2.3-Å and 1.7-Å resolutions, respectively, reveal that the MDM2 peptide recognizes the same surface groove in HAUSP as that recognized by p53 but mediates more extensive interactions. Structural comparison led to the identification of a consensus peptide-recognition sequence by HAUSP. These results, together with the structure of a combined substrate-binding-and-deubiquitylation domain of HAUSP, provide important insights into regulation of the p53–MDM2 pathway by HAUSP.