In eukaryotes, protein function can be modulated by ligation to ubiquitin or to ubiquitin-like proteins (Ubl proteins). The vertebrate Ubl protein SUMO-1 is only 18% identical to ubiquitin but is 48% identical to the yeast protein Smt3. Both SUMO-1 and Smt3 are ligated to cellular proteins, and protein conjugation to SUMO-1/Smt3 is involved in many physiological processes. It remained unknown, however, whether deconjugation of SUMO-1/Smt3 from proteins is also essential. Here we describe a yeast Ubl-specific protease, Ulp1, which cleaves proteins from Smt3 and SUMO-1 but not from ubiquitin. Ulp1 is unrelated to any known deubiquitinating enzyme but shows distant similarity to certain viral proteases, indicating the existence of a widely conserved protease fold. Proteins related to Ulp1 are present in many organisms, including several human pathogens. The pattern of Smt3-coupled proteins in yeast changes markedly throughout the cell cycle, and specific conjugates accumulate in ulp1 mutants. Ulp1 has several functions, including an essential role in the G2/M phase of the cell cycle.