Saturn's largest satellite, Titan, has a massive nitrogen atmosphere containing up to 5 per cent methane near its surface. Photochemistry in the stratosphere would remove the present-day atmospheric methane in a few tens of millions of years. Before the Cassini-Huygens mission arrived at Saturn, widespread liquid methane or mixed hydrocarbon seas hundreds of metres in thickness were proposed as reservoirs from which methane could be resupplied to the atmosphere over geologic time. Titan fly-by observations and ground-based observations rule out the presence of extensive bodies of liquid hydrocarbons at present, which means that methane must be derived from another source over Titan's history. Here we show that episodic outgassing of methane stored as clathrate hydrates within an icy shell above an ammonia-enriched water ocean is the most likely explanation for Titan's atmospheric methane. The other possible explanations all fail because they cannot explain the absence of surface liquid reservoirs and/or the low dissipative state of the interior. On the basis of our models, we predict that future fly-bys should reveal the existence of both a subsurface water ocean and a rocky core, and should detect more cryovolcanic edifices.