Climate change driven ocean warming is a worldwide environmental issue that can impact cycling of greenhouse gases. However, how methane production in marine sediments as a potential contributor to atmospheric greenhouse gases versus its consumption at the sulfate–methane transition zone will be affected by climate change related warming is still not well constrained. In this study, sediments from two Baltic Sea bays with long-term temperature differences were collected during summer and winter. The primary difference between the two bays was that one had been heated by a nearby power plant for 50 years, resulting in a 5.1 °C increase in annual average temperature compared to an unheated control bay. The results showed that near-seafloor sediment methane concentrations were 50 times higher compared to present-day conditions. Furthermore, the sediment fluxes along with microbial community composition changes suggested that long-term warming may thin the sulfate reduction zone, such that methanotrophic archaea and sulfate reducing bacteria peaked at shallower sediment depths in the heated bay. Overall, the results from long-term warming in natural sediment environment indicated that future climate change warming may increase the risk of methane release to the water and eventually the atmosphere.