Atmospheric methane is an important greenhouse gas and a sensitive indicator of climate change and millennial-scale temperature variability. Its concentrations over the past 650,000 years have varied between ∼350 and ∼800 parts per 109 by volume (p.p.b.v.) during glacial and interglacial periods, respectively. In comparison, present-day methane levels of ∼1,770 p.p.b.v. have been reported. Insights into the external forcing factors and internal feedbacks controlling atmospheric methane are essential for predicting the methane budget in a warmer world. Here we present a detailed atmospheric methane record from the EPICA Dome C ice core that extends the history of this greenhouse gas to 800,000 yr before present. The average time resolution of the new data is ∼380 yr and permits the identification of orbital and millennial-scale features. Spectral analyses indicate that the long-term variability in atmospheric methane levels is dominated by ∼100,000 yr glacial-interglacial cycles up to ∼400,000 yr ago with an increasing contribution of the precessional component during the four more recent climatic cycles. We suggest that changes in the strength of tropical methane sources and sinks (wetlands, atmospheric oxidation), possibly influenced by changes in monsoon systems and the position of the intertropical convergence zone, controlled the atmospheric methane budget, with an additional source input during major terminations as the retreat of the northern ice sheet allowed higher methane emissions from extending periglacial wetlands. Millennial-scale changes in methane levels identified in our record as being associated with Antarctic isotope maxima events are indicative of ubiquitous millennial-scale temperature variability during the past eight glacial cycles. ©2008 Nature Publishing Group.