Methane (CH4) emissions from Arctic lakes are of global concern in a warming world. Past Holocene warming provides an opportunity to examine carbon-climate feedbacks that develop over hundreds to thousands of years, but thus far records of past long-term changes in lake CH4 dynamics are rare. Here, we demonstrate for the first time that the hydrogen stable isotopic composition of aquatic plant wax records incorporation of CH4 in plant (aquatic moss) biomass. Trends in δ2H and δ13C values of aquatic plant derived leaf waxes point to widespread and sustained middle Holocene shifts in CH4 cycling at climatically diverse sites across Greenland during millennia of elevated summer temperatures. Independent proxies indicate concurrent increases in local primary productivity and decreases in hypolimnetic oxygen. These data portend that ongoing warming may promote an enduring shift towards conditions that enhance methanogenesis in many Arctic lakes, including in lakes where these conditions do not exist today. This work highlights a previously unrecognized factor influencing δ2H values of aquatic leaf waxes in some high-latitude lakes, and also draws attention to the role of common aquatic mosses as a potentially important sink of lake CH4 across the Arctic that has yet to be quantified.