Coastal marine sediments harbor vast amounts of the potent greenhouse gas methane, yet, most methane does not escape the seabed but is oxidized to CO2 with sulfate as the oxidant. This microbially mediated oxidation takes place within the sulfate–methane transition (SMT), a sediment horizon where the downward diffusive flux of sulfate encounters the upward flux of methane. We identified a systematic discrepancy between the fluxes of sulfate and methane into the SMT across multiple sites in the Baltic Sea, such that more sulfate was consumed than would be expected from the 1:1 stoichiometry of anaerobic methane oxidation with sulfate. The magnitude of this flux discrepancy was consistent with the rate of mineralization of buried organic C in the SMT. This conclusion was corroborated by stable C isotope budgets. Detailed radiotracer experiments showed that about 20–60% of the organic C degradation within the SMT took place through methane, which was then oxidized to CO2 by sulfate reduction. Such a previously unrecognized ‘cryptic’ CH4 cycling in the SMT was not discernible from geochemical profiles due to the concurrent net CH4 consumption. Sedimentary gene pools suggested that ANME-1 archaea were responsible for both the methane oxidation and methane production.