All members of the herpesviridae contain within their large tegument protein a cysteine protease module that displays deubiquitinating activity. We report the crystal structure of the cysteine protease domain of murine cytomegalovirus M48 (M48 USP) in a complex with a ubiquitin (Ub)-based suicide substrate. M48 USP adopts a papain-like fold, with the active-site cysteine forming a thioether linkage to the suicide substrate. The Ub core participates in an extensive hydrophobic interaction with an exposed β hairpin loop of M48 USP. This Ub binding mode contributes to Ub specificity and is distinct from that observed in other deubiquitinating enzymes. Both the arrangement of active-site residues and the architecture of the interface with Ub lead us to classify this domain as the founding member of a previously unknown class of deubiquitinating enzymes.