A classical approach, protein separation by two-dimensional blue native/sodium dodecyl sulfate-polyacrylamide gel electrophoresis, was combined with tandem mass spectrometry and up-to-date computer technology to characterize the mitochondrial "protein complex proteome" of Arabidopsis (Arabidopsis thaliana) in so far unrivaled depth. We further developed the novel GelMap software package to annotate and evaluate two-dimensional blue native/sodium dodecyl sulfate gels. The software allows (1) annotation of proteins according to functional and structural correlations (e.g. subunits of a distinct protein complex), (2) assignment of comprehensive protein identification lists to individual gel spots, and thereby (3) selective display of protein complexes of low abundance. In total, 471 distinct proteins were identified by mass spectrometry, several of which form part of at least 35 different mitochondrial protein complexes. To our knowledge, numerous protein complexes were described for the first time (e.g. complexes including pentatricopeptide repeat proteins involved in nucleic acid metabolism). Discovery of further protein complexes within our data set is open to everybody via the public GelMap portal at www.gelmap.de/arabidopsis_mito.