ThiS is a sulfur carrier protein that plays a central role in thiamin biosynthesis in Escherichia coli. Here we report the solution NMR structure of ThiS, the first for this class of sulfur carrier proteins. Although ThiS shares only 14% sequence identity with ubiquitin, it possesses the ubiquitin fold. This structural homology, combined with established functional similarities involving sulfur chemistry, demonstrates that the eukaryotic ubiquitin and the prokaryotic ThiS evolved from a common ancestor. This illustrates how structure determination is essential in establishing evolutionary links between proteins in which structure and function have been conserved through eons of evolution despite loss of sequence identity. The ThiS structure reveals both hydrophobic and electrostatic surface features that are likely determinants for interactions with binding partners. Comparison with surface features of ubiquitin and ubiquitin homologs SUMO-1, RUB-1 and NEDD8 suggest how Nature has utilized this single fold to incorporate similar chemistry into a broad array of highly specific biological processes.