Due to fierce competition for resources, soil bacteria are often starved of conventional energy sources. To cope with this, many bacteria have evolved to persist using alternative energy sources including the trace quantities of carbon monoxide (CO) present in the atmosphere. To do this, they utilise a specialised enzyme called molybdenum-copper carbon monoxide dehydrogenase (Mo-CODH), which oxidises CO to produce high-energy electrons. We isolated the high-affinity Mo-CODH from the soil bacterium Mycobacterium smegmatis and determined the structure to a resolution of 1.85 Å, using CryoEM. We found that Mo-CODH is a soluble enzyme with no membrane-associated regions. However, to provide energy to the cell for respiration it must transfer electrons derived from CO oxidation to the hydrophobic electron transport molecule menaquinone, which is localised in the cell membrane. Previously, in another bacterial species, an accessory protein encoded in the Mo-CODH operon was implicated in the localisation of Mo-CODH to the cell membrane. We used X-ray crystallography to determine the structure of this uncharacterised lipid-anchored protein called CoxG. Interestingly, CoxG contains a hydrophobic cavity, which specifically binds menaquinone in M. smegmatis. AlphaFold modelling demonstrated that CoxG binds to Mo-CODH within proximity of Mo-CODH’s FAD group, the terminal point of electron transfer after CO oxidation. We demonstrated in M. smegmatis cells that CoxG is critical for CO oxidation and salt bridges between the two proteins drive their interaction. We determined that the role of CoxG is a menaquinone shuttle protein, delivering menaquinone from the membrane to Mo-CODH and returning the reduced menaquinol. Finally, we show that the association between CoxG and Mo-CODH is present across diverse bacterial and archaeal species, demonstrating the importance of this long range quinone transport for energy conservation.