Biogenesis of mitochondrial cytochrome c oxidase (COX) relies on a large number of assembly factors, among them the transmembrane protein Surf1. The loss of human Surf1 function is associated with Leigh syndrome, a fatal neurodegenerative disorder caused by severe COX deficiency. In the bacterium Paracoccus denitrificans, two homologous proteins, Surf1c and Surf1q, were identified, which we characterize in the present study. When coexpressed in Escherichia coli together with enzymes for heme a synthesis, the bacterial Surf1 proteins bind heme a in vivo. Using redox difference spectroscopy and isothermal titration calorimetry, the binding of the heme cofactor to purified apo-Surf1c and apo-Surf1q is quantified: Each of the Paracoccus proteins binds heme a in a 1:1 stoichiometry and with Kd values in the submicromolar range. In addition, we identify a conserved histidine as a residue crucial for heme binding. Contrary to most earlier concepts, these data support a direct role of Surf1 in heme a cofactor insertion into COX subunit I by providing a protein-bound heme a pool.