Complex I (NADH:ubiquinone oxidoreductase) is the largest enzyme of the mitochondrial respiratory chain. Compared to its bacterial counterpart which encompasses 14-17 subunits, mitochondrial complex I has almost tripled its subunit composition during evolution of eukaryotes, by recruitment of so-called accessory subunits, part of them being specific to distinct evolutionary lineages. The increasing availability of numerous broadly sampled eukaryotic genomes now enables the reconstruction of the evolutionary history of this large protein complex. Here, a combination of profile-based sequence comparisons and basic structural properties analyses at the protein level enabled to pinpoint homology relationships between complex I subunits from fungi, mammals or green plants, previously identified as "lineage-specific" subunits. In addition, homologs of at least 40 mammalian complex I subunits are present in representatives of all major eukaryote assemblages, half of them having not been investigated so far (Excavates, Chromalveolates, Amoebozoa). This analysis revealed that complex I was subject to a phenomenal increase in size that predated the diversification of extant eukaryotes, followed by very few lineage-specific additions/losses of subunits. The implications of this subunit conservation for studies of complex I are discussed.