Skp1 (S-phase kinase-associated protein 1) is a core component of SCF ubiquitin ligases and mediates protein degradation, thereby regulating eukaryotic fundamental processes such as cell cycle progression, transcriptional regulation, and signal transduction. Among the four components of the SCF complexes, Rbx1 and Cullin form a core catalytic complex, an F-box protein acts as a receptor for target proteins, and Skp1 is an adaptor between one of the variable F-box proteins and Cullin. Whereas protists, fungi, and some vertebrates have a single SKP1 gene, many animal and plant species possess multiple SKP1 homologs. It has been shown that the same Skp1 homolog can interact with two or more F-box proteins, and different Skp1 homologs from the same species sometimes can interact with the same F-box protein. In this paper, we demonstrate that multiple Skp1 homologs from the same species have evolved at highly heterogeneous rates. Parametric bootstrap analyses suggested that the differences in evolutionary rate are so large that true phylogenies were not recoverable from the full data set. Only when the original data set were partitioned into sets of genes with slow, medium, and rapid rates of evolution and analyzed separately, better-resolved relationships were observed. The slowly evolving Skp1 homologs, which are relatively highly conserved in sequence and expressed widely and/or at high levels, usually have very low d(N)/d(S) values, suggesting that they have evolved under functional constraint and serve the most fundamental function(s). On the other hand, the rapidly evolving members are structurally more diverse and usually have limited expression patterns and higher d(N)/d(S) values, suggesting that they may have evolved under relaxed or altered constraint, or even under positive selection. Some rapidly evolving members may have lost their original function(s) and/or acquired new function(s) or become pseudogenes, as suggested by their expression patterns, d(N)/d(S) values, and amino acid changes at key positions. In addition, our analyses revealed several monophyletic groups within the SKP1 gene family, one for each of protists, fungi, animals, and plants, as well as nematodes, arthropods, and angiosperms, suggesting that the extant SKP1 genes within each of these eukaryote groups shared only one common ancestor.