Many soil bacteria lack the organic compounds required for growth and, as a result, exist in a dormant non-replicative state. In this state, bacteria still need a low level of energy for cell maintenance and to maintain a proton motive force. Bacteria oxidise reduced trace gases in the atmosphere to obtain this energy, most notably hydrogen (H2) and carbon monoxide (CO). The low potential electrons from this process enter the cellular respiratory chain, contributing to proton motive force and ATP generation. While these gases are present in the atmosphere at extremely low levels (530 parts per billion for H2), they represent a ubiquitous and dependable energy source. Atmospheric H2 oxidation is mediated by members of the [NiFe]-hydrogenase superfamily. However, it is unclear how these enzymes overcome the extraordinary catalytic challenge of selectively oxidising picomolar levels of H2 amid ambient levels of O2, a potent inhibitor of the [NiFe]-hydrogenase catalytic cluster. In this work, we have determined the 1.52 Å resolution CryoEM structure of the mycobacterial hydrogenase Huc and investigated its mechanism. We show that Huc is an oxygen-insensitive enzyme that couples the oxidation of atmospheric H2 at its large subunit to the hydrogenation of the respiratory electron carrier menaquinone at its small subunit. The enzyme uses a narrow hydrophobic gas channel to selectively bind atmospheric H2 while excluding O2, contributing to the oxygen insensitivity of this enzyme. Three [3Fe-4S] clusters and their unusual ligation by a D-histidine modulate the electrochemical properties of the enzyme such that atmospheric H2 oxidation is energetically feasible. Huc forms an 833 kDa complex composed of an octamer of catalytic subunits around a tetrameric membrane-associated central stalk, which extracts and transports menaquinone a remarkable 94 Å from the membrane, enabling its reduction. This work provides a mechanistic basis for the biogeochemically and ecologically important process of atmospheric H2 oxidation and uncovers a novel mode of energy coupling dependent on long-range quinone transport, providing a basis for developing biocatalysts that oxidise H2 in ambient air.