Mitochondria exert an immense amount of cytophysiological functions, but the structural basis of most of these processes is still poorly understood. Here we use cross-linking mass spectrometry to probe the organization of proteins in native mouse heart mitochondria. Our approach provides the largest survey of mitochondrial protein interactions reported so far. In total, we identify 3,322 unique residue-to-residue contacts involving half of the mitochondrial proteome detected by bottom-up proteomics. The obtained mitochondrial protein interactome gives insights in the architecture and submitochondrial localization of defined protein assemblies, and reveals the mitochondrial localization of four proteins not yet included in the MitoCarta database. As one of the highlights, we show that the oxidative phosphorylation complexes I-V exist in close spatial proximity, providing direct evidence for supercomplex assembly in intact mitochondria. The specificity of these contacts is demonstrated by comparative analysis of mitochondria after high salt treatment, which disrupts the native supercomplexes and substantially changes the mitochondrial interactome.