Protein modifiers are involved in diverse biological processes and regulate the activity or function of target proteins by covalently conjugating to them. Although ubiquitin and a number of ubiquitin-like protein modifiers (Ubls) in eukaryotes have been identified, no protein modifier has been found in prokaryotes; thus, their evolutionary origin remains a puzzle. To infer the evolutionary relationships between the protein modifiers and sulfur carrier proteins, we solved the solution NMR structure of the Urm1 (ubiquitin-related modifier-1) protein from Saccharomyces cerevisiae. Both structural comparison and phylogenetic analysis of the ubiquitin superfamily, with emphasis on the Urm1 family, indicate that Urm1 is the unique "molecular fossil" that has the most conserved structural and sequence features of the common ancestor of the entire superfamily. The similarities of 3D structure and hydrophobic and electrostatic surface features between Urm1 and MoaD (molybdopterin synthase small subunit) suggest that they may interact with partners in a similar manner, and similarities between Urm1-Uba4 and MoaD-MoeB establish an evolutionary link between ATP-dependent protein conjugation in eukaryotes and ATP-dependent cofactor sulfuration.