Ubiquitination of proteins modifies protein function by either altering their activities, promoting their degradation, or altering their subcellular localization. Deubiquitinating enzymes are proteases that reverse this ubiquitination. Previous studies demonstrate that proteins that contain an ovarian tumor (OTU) domain possess deubiquitinating activity. This domain of approximately 130 amino acids is weakly similar to the papain family of proteases and is highly conserved from yeast to mammals. Here we report structural and functional studies on the OTU domain-containing protein from yeast, Otu1. We show that Otu1 binds polyubiquitin chain analogs more tightly than monoubiquitin and preferentially hydrolyzes longer polyubiquitin chains with Lys(48) linkages, having little or no activity on Lys(63)- and Lys(29)-linked chains. We also show that Otu1 interacts with Cdc48, a regulator of the ER-associated degradation pathway. We also report the x-ray crystal structure of the OTU domain of Otu1 covalently complexed with ubiquitin and carry out structure-guided mutagenesis revealing a novel mode of ubiquitin recognition and a variation on the papain protease catalytic site configuration that appears to be conserved within the OTU family of ubiquitin hydrolases. Together, these studies provide new insights into ubiquitin binding and hydrolysis by yeast Otu1 and other OTU domain-containing proteins.