Mitochondria have crucial roles in cellular energetics, metabolism, signalling and quality control^1–4. They contain around 1,000 different proteins that often assemble into complexes and supercomplexes such as respiratory complexes and preprotein translocases^1,3–7. The composition of the mitochondrial proteome has been characterized^1,3,5,6; however, the organization of mitochondrial proteins into stable and dynamic assemblies is poorly understood for major parts of the proteome^1,4,7. Here we report quantitative mapping of mitochondrial protein assemblies using high-resolution complexome profiling of more than 90% of the yeast mitochondrial proteome, termed MitCOM. An analysis of the MitCOM dataset resolves >5,200 protein peaks with an average of six peaks per protein and demonstrates a notable complexity of mitochondrial protein assemblies with distinct appearance for respiration, metabolism, biogenesis, dynamics, regulation and redox processes. We detect interactors of the mitochondrial receptor for cytosolic ribosomes, of prohibitin scaffolds and of respiratory complexes. The identification of quality-control factors operating at the mitochondrial protein entry gate reveals pathways for preprotein ubiquitylation, deubiquitylation and degradation. Interactions between the peptidyl-tRNA hydrolase Pth2 and the entry gate led to the elucidation of a constitutive pathway for the removal of preproteins. The MitCOM dataset—which is accessible through an interactive profile viewer—is a comprehensive resource for the identification, organization and interaction of mitochondrial machineries and pathways.