Diverse aerobic bacteria use atmospheric H2 as an energy source for growth and survival1. This globally significant process regulates the composition of the atmosphere, enhances soil biodiversity and drives primary production in extreme environments2,3. Atmospheric H2 oxidation is attributed to uncharacterized members of the [NiFe] hydrogenase superfamily4,5. However, it remains unresolved how these enzymes overcome the extraordinary catalytic challenge of oxidizing picomolar levels of H2 amid ambient levels of the catalytic poison O2 and how the derived electrons are transferred to the respiratory chain1. Here we determined the cryo-electron microscopy structure of the Mycobacterium smegmatis hydrogenase Huc and investigated its mechanism. Huc is a highly efficient oxygen-insensitive enzyme that couples oxidation of atmospheric H2 to the hydrogenation of the respiratory electron carrier menaquinone. Huc uses narrow hydrophobic gas channels to selectively bind atmospheric H2 at the expense of O2, and 3 [3Fe–4S] clusters modulate the properties of the enzyme so that atmospheric H2 oxidation is energetically feasible. The Huc catalytic subunits form an octameric 833 kDa complex around a membrane-associated stalk, which transports and reduces menaquinone 94 Å from the membrane. These findings provide a mechanistic basis for the biogeochemically and ecologically important process of atmospheric H2 oxidation, uncover a mode of energy coupling dependent on long-range quinone transport, and pave the way for the development of catalysts that oxidize H2 in ambient air. Structural and biochemical studies of the Mycobacterium smegmatis hydrogenase Huc provides insights into how [NiFe] hydrogenases oxidize trace amounts of atmospheric hydrogen and transfer the electrons liberated via quinone transport.