Combining mass spectrometry based chemical cross-linking and complexome profiling, we analyzed the interactome of heart mitochondria. We focused on complexes of oxidative phosphorylation and found that dimeric apoptosis inducing factor 1 (AIFM1) forms a defined complex with ~10% of monomeric cytochrome c oxidase (COX), but hardly interacts with respiratory chain supercomplexes. Multiple AIFM1 inter-crosslinks engaging six different COX subunits provided structural restraints to build a detailed atomic model of the COX-AIFM12 complex. Application of two complementary proteomic approaches thus provided unexpected insight into the macromolecular organization of the mitochondrial complexome. Our structural model excludes direct electron transfer between AIFM1 and COX. Notably however, the binding site of cytochrome c remains accessible allowing formation of a ternary complex. The discovery of the previously overlooked COX-AIFM12 complex and clues provided by the structural model hint at a role of AIFM1 in OXPHOS biogenesis and in programmed cell death.