High concentrations of the greenhouse gases CO2 and CH4 have long been invoked to explain a largely ice-free climate despite lower solar luminosity during the Precambrian. However, recently a “methane paradox” has emerged, whereby the atmospheric CH4 abundances required to buffer the Proterozoic climate system are difficult to reproduce in global biogeochemical models. Here, we use a biogeochemical model of a microbial mat ecosystem to examine whether terrestrial cyanobacteria-rich sediments (mats) could have released significant amounts of CH4 to the atmosphere under the low pO2 conditions characteristic of most of Precambrian time. We then use these fluxes to inform an Earth system model inversion of the extent of microbial mat coverage on Earth’s land surface that would be required to buffer mid-Proterozoic climate. Terrestrial mats on as little ∼8%–10% of the exposed land surface result in a clement climate state. Further, although the photochemical stability of CH4 in the atmosphere increases as atmospheric oxygen levels rise, methane fluxes from mat ecosystems drop dramatically, suggesting novel links between planetary oxygenation and catastrophic climate instability during the Proterozoic.