Ubiquitin belongs to an important class of protein modifier and gene expression regulator proteins that participates in various cellular processes. A large number of ubiquitin-related proteins have been identified during the last two decades. However, the evolutionary history of this ancient gene family remains largely unknown. We analyzed the members of the superfamily using both sequence- and structure-based methodology to better understand the evolution of ubiquitin-related proteins. As a part of these analyses we used the MEME algorithm to extract common sequence motifs across the superfamily, and we inferred the phylogeny and distribution of the superfamily members across multiple species. A total of 23 families were identified in the gene family. Several common sequence motifs were revealed and evaluated. We also found that the number of genes for ubiquitin-related proteins encoded within a specific genome correlates with the biological complexity of that particular species. This analysis should provide valuable insight into the sequence/function relationships and evolutionary history of ubiquitin and ubiquitin-related proteins.