The boundary between ice and basalt on Earth is an analogue for some near-surface environments of Mars. We investigated neutrophilic iron-oxidizing microorganisms from the basalt-ice interface in a lava tube from the Oregon Cascades with perennial ice. One of the isolates (Pseudomonas sp. HerB) can use ferrous iron Fe(II) from the igneous mineral olivine as an electron donor and O(2) as an electron acceptor. The optimum growth temperature is ∼12-14°C, but growth also occurs at 5°C. Bicarbonate is a facultative source of carbon. Growth of Pseudomonas sp. HerB as a chemolithotrophic iron oxidizer with olivine as the source of energy is favored in low O(2) conditions (e.g., 1.6% O(2)). Most likely, microbial oxidation of olivine near pH 7 requires low O(2) to offset the abiotic oxidation of iron. The metabolic capabilities of this bacterium would allow it to live in near-surface, icy, volcanic environments of Mars in the present or recent geological past and make this type of physiology a prime candidate in the search for life on Mars.