Spatial variability of methane (CH4) on Mars suggests the presence of localized subsurface sources. Here, we show that olivine hydration in the Martian regolith and crust may be a major CH4 source, which contributed significantly to the warming of early Mars. Methane production is kinetically and thermodynamically favored during low-T aqueous alteration of olivine-rich rocks. Sustained release of CH4 on present-day Mars may come through the breakdown of ancient CH4 hydrates and from springs driven by geothermal heat.