The endosymbiotic origin of mitochondria has resulted in a massive horizontal transfer of genetic material from an alpha-proteobacterium to the early eukaryotes. Using large-scale phylogenetic analysis we have previously identified 630 orthologous groups of proteins derived from this event. Here we show that this proto-mitochondrial protein set has undergone extensive lineage-specific gene loss in the eukaryotes, with an average of three losses per orthologous group in a phylogeny of nine species. This gene loss has resulted in a high variability of the alphaproteobacterial-derived gene content of present-day eukaryotic genomes that might reflect functional adaptation to different environments. Proteins functioning in the same biochemical pathway tend to have a similar history of gene loss events, and we use this property to predict functional interactions among proteins in our set.