Establishing whether past millennial-scale climate change affected the stability of marine methane hydrate is important for our understanding of climatic change and determining the fate of marine hydrates in a future warmer world. We show, using three-dimensional seismic data offshore of Mauritania, that episodic, millennial-scale shifts of the base of the hydrate stability zone can be imaged below the ocean floor. Process modeling suggests that the base of the hydrate stability zone should have shallowed and deepened in response to climate change over the past ∼150,000 yr. Specifically, there is seismic evidence for millennial-scale shifts during the Holocene (∼11,700 yr ago to present) at a temporal resolution that has previously been unrealized. This is the first evidence that millennial-scale climatic cycles caused hydrate formation and dissociation and that hydrate instability should be expected in a warming world.