The rotenone-sensitive NADH:ubiquinone oxidoreductase (complex I) is the most intricate membrane-bound enzyme of the mitochondrial respiratory chain. Notably the bovine enzyme comprises up to 46 subunits, while 27 subunits could be considered as widely conserved among eukaryotic complex I. By combining proteomic and genomic approaches, we characterized the complex I composition from the unicellular green alga Chlamydomonas reinhardtii. After purification by blue-native polyacrylamide gel electrophoresis (BN-PAGE), constitutive subunits were analyzed by SDS-PAGE coupled to tandem mass spectrometry (MS) that allowed the identification of 30 proteins. We compared the known complex I components from higher plants, mammals, nematodes and fungi with this MS data set and the translated sequences from the algal genome project. This revealed that the Chlamydomonas complex I is likely composed of 42 proteins, for a total molecular mass of about 970 kDa. In addition to the 27 typical components, we have identified four new complex I subunit families (bovine ESSS, PFFD, B16.6, B12 homologues), extending the number of widely conserved eukaryote complex I components to 31. In parallel, our analysis showed that a variable number of subunits appears to be specific to each eukaryotic kingdom (animals, fungi or plants). Protein sequence divergence in these kingdom-specific sets is significant and currently we cannot exclude the possibility that homology between them exists, but has not yet been detected.