Cytochromes c are ubiquitous proteins, essential for life in most organisms. Their distinctive characteristic is the covalent attachment of heme to their polypeptide chain. This post-translational modification is performed by a dedicated protein system, which in many Gram-negative bacteria and plant mitochondria is a nine-protein apparatus (CcmA–I) called System I. Despite decades of study, mechanistic understanding of the protein–protein interactions in this highly complex maturation machinery is still lacking. Here, we focused on the interaction of CcmC, the protein that sources the heme cofactor, with CcmE, the pivotal component of System I responsible for the transfer of the heme to the apocytochrome. Using in silico analyses, we identified a putative interaction site between these two proteins (residues Asp47, Gln50, and Arg55 on CcmC; Arg73, Asp101, and Glu105 on CcmE), and we validated our findings by in vivo experiments in Escherichia coli. Moreover, employing NMR spectroscopy, we examined whether a heme-binding site on CcmE contributes to this interaction and found that CcmC and CcmE associate via protein–protein rather than protein–heme contacts. The combination of in vivo site-directed mutagenesis studies and high-resolution structural techniques enabled us to determine at the residue level the mechanism for the formation of one of the key protein complexes for cytochrome c maturation by System I.