Knowledge of taxis (directed swimming) in the Archaea is currently expanding through identification of novel receptors, effectors, and proteins involved in signal transduction to the flagellar motor. Although the ability for biological cells to sense and swim toward hydrogen gas has been hypothesized for many years, this capacity has yet to be observed and demonstrated. Here we show that the average swimming velocity increases in the direction of a source of hydrogen gas for the methanogen, Methanococcus maripaludis using a capillary assay with anoxic gas-phase control and time-lapse microscopy. The results indicate that a methanogen couples motility to hydrogen concentration sensing and is the first direct observation of hydrogenotaxis in any domain of life. Hydrogenotaxis represents a strategy that would impart a competitive advantage to motile microorganisms that compete for hydrogen gas and would impact the C, S and N cycles.