Genetic variation is the major mechanism behind adaptation and evolutionary change. As most proteins operate through interactions with other proteins, changes in protein complex composition and subunit sequence provide potentially new functions. Comparative genomics can reveal expansions, losses and sequence divergence within protein-coding genes, but in silico analysis cannot detect subunit substitutions or replacements of entire protein complexes. Insights into these fundamental evolutionary processes require broad and extensive comparative analyses, from both in silico and experimental evidence. Here, we combine data from both approaches and consider the gamut of possible protein complex compositional changes that arise during evolution, citing examples of complete conservation to partial and total replacement by functional analogues. We focus in part on complexes in trypanosomes as they represent one of the better studied non-animal/non-fungal lineages, but extend insights across the eukaryotes by extensive comparative genomic analysis. We argue that gene loss plays an important role in diversification of protein complexes and hence enhancement of eukaryotic diversity.