Turnip yellow mosaic virus (TYMV)--a member of the alphavirus-like supergroup of viruses--serves as a model system for positive-stranded RNA virus membrane-bound replication. TYMV encodes a precursor replication polyprotein that is processed by the endoproteolytic activity of its internal cysteine proteinase domain (PRO). We recently reported that PRO is actually a multifunctional enzyme with a specific ubiquitin hydrolase (DUB) activity that contributes to viral infectivity. Here, we report the crystal structure of the 150-residue PRO. Strikingly, PRO displays no homology to other processing proteinases from positive-stranded RNA viruses, including that of alphaviruses. Instead, the closest structural homologs of PRO are DUBs from the Ovarian tumor (OTU) family. In the crystal, one molecule's C-terminus inserts into the catalytic cleft of the next, providing a view of the N-terminal product complex in replication polyprotein processing. This allows us to locate the specificity determinants of PRO for its proteinase substrates. In addition to the catalytic cleft, at the exit of which the active site is unusually pared down and solvent-exposed, a key element in molecular recognition by PRO is a lobe N-terminal to the catalytic domain. Docking models and the activities of PRO and PRO mutants in a deubiquitylating assay suggest that this N-terminal lobe is also likely involved in PRO's DUB function. Our data thus establish that DUBs can evolve to specifically hydrolyze both iso- and endopeptide bonds with different sequences. This is achieved by the use of multiple specificity determinants, as recognition of substrate patches distant from the cleavage sites allows a relaxed specificity of PRO at the sites themselves. Our results thus shed light on how such a compact protein achieves a diversity of key functions in viral genome replication and host-pathogen interaction.