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 trace quantities of carbon monoxide gas (CO) present in the atmosphere. We isolated the enzyme responsible for this process, carbon monoxide dehydrogenase (CODH), from the soil bacterium Mycobacterium smegmatis to investigate how it drives respiration during starvation. Utilising cryoEM we found that CODH is a soluble enzyme with no membrane-associated regions. However, to provide energy to the cell CODH must transfer electrons derived from CO to the hydrophobic electron transport molecule menaquinone, which is localised in the cell membrane. Interestingly, within the operon encoding CODH is a gene encoding a single pass transmembrane protein called CoxG, which is critical for CODH activity. Structural characterisation of CoxG showed it contains a hydrophobic cavity that specifically binds menaquinone in M. smegmatis. AlphaFold2 modelling demonstrated that CoxG and CODH interact, and their interaction interface allows for transfer of electrons from CODH to the menaquinone within CoxG. M. smegmatis cells lacking CoxG could no longer oxidise CO, however when supplemented with an artificial electron acceptor, CODH regained activity. Based on these data we propose a model where CoxG is a menaquinone shuttle protein that extracts menaquinone from the membrane and delivers it to CODH. The interaction between CoxG and CODH is conserved across many different bacterial and archaeal species and this interaction is critical for CO mediated respiration and the survival of these organisms.