Joseph-Machado is an incurable neurodegenerative disease caused by toxic aggregation of ataxin-3, a ubiquitin-specific cysteine protease, involved in the ubiquitin-proteasome pathway and known to bind poly-ubiquitin chains of four or more subunits. The enzymatic site resides in the N-terminal josephin domain of ataxin-3. We have characterized the ubiquitin-binding properties of josephin and showed that, unexpectedly, josephin contains two contiguous but distinct ubiquitin-binding sites. One is close to the enzymatic cleft and exploits an induced fit mechanism, which involves a flexible helical hairpin; the other overlaps with the site involved in recognition of HHR23B, a protein involved in delivering proteolytic substrates to the proteasome. To gain a structural description of the system, we had to overcome the nontrivial problem of dealing with a weak ternary complex. This was done by designing josephin mutants, which retain only one binding site and by characterizing the complexes with complementary computational and experimental techniques. The presence of two ubiquitin-binding sites explains how ataxin-3 binds poly-ubiquitin chains and provides new insights into the molecular mechanism of ubiquitin recognition.