Past atmospheric methane-concentration oscillations recorded in polar ice cores vary together with rapid global climatic changes during the last glacial episode. In the "clathrate gun hypothesis," massive releases of deep-sea methane from marine gas-hydrate dissociation led to these well known, global, abrupt warmings in the past. If evidence for such releases in the water column exists, however, the mechanism and eventual transfer to the atmosphere has not yet been documented clearly. Here we describe a high-resolution marine-sediment record of stable carbon isotopic changes from the Papua Gulf, off Papua New Guinea, which exhibits two extremely depleted excursions (down to -9 per thousand ) at approximately 39,000 and approximately 55,000 years. Morphological, isotopic, and trace metal evidence dismisses authigenic calcite as the main source of depleted carbon. Massive methane release associated with deep-sea gas-hydrate dissociation is the most likely cause for such large depletions of delta(13)C. The absence of a delta(13)C gradient in the water column during these events implies that the methane rose through the entire water column, reaching the sea-air interface and thus the atmosphere. Foraminiferal delta(18)O composition suggests that the rise of the methane in the water column created an upwelling flow. These inferred emission events suggest that during the last glacial episode, this process was likely widespread, including tropical regions. Thus, the release of methane from the ocean floor into the atmosphere cannot be dismissed as a strong positive feedback in climate dynamics processes.