Ubiquitin-fold modifier 1 (Ufm1) is a newly identified ubiquitin-like protein. Like ubiquitin and other ubiquitin-like proteins, Ufm1 is synthesized as a precursor that needs to be processed to expose the conserved C-terminal glycine prior to its conjugation to target proteins. Two novel proteases, named UfSP1 and UfSP2, have been shown to be responsible for the release of Ufm1 from Ufm1-conjugated cellular proteins as well as for the processing of its precursor. They show no sequence homology with known proteases. Here, we describe the 1.7A resolution crystal structure of mouse UfSP1, consisting of 217 amino acids. The structure reveals that it is a novel cysteine protease having a papain-like fold, with Cys(53), Asp(175), and His(177) that form a catalytic triad, and Tyr(41) that participates in the formation of the oxyanion hole. This differs from the canonical catalytic triad of papain-like proteases in that the aspartate and the histidine residues are from the "Asp-Pro-His" box. The Asp-Pro-His configuration seen in UfSP1, together with Atg4B and M48(USP), seem to form a new subfamily of the cysteine protease superfamily. The mutagenesis study of the active site residues confirms structural basis for catalysis. The interaction between UfSP1 and Ufm1 appears quite substantial, since the K(D) value was estimated to be 1.6 mum by the isothermal titration calorimetry analysis. Furthermore, the NMR data shows that the loop between beta3 and alpha2 in addition to the C-terminal region of Ufm1 plays a role in binding to UfSP1.