Methane is a potent greenhouse gas that has contributed approximately 20 to the Earth s warming since pre-industrial times. The world s oceans are an important source of methane, comprising 1-4 of annual global emissions. But despite its global significance, oceanic methane production is poorly understood. In particular, methane concentrations in the surface waters of most of the world s oceans are supersaturated with respect to atmospheric concentrations, but the origin of this methane, which has been thought to be produced exclusively in anaerobic environments, is not known. Here, we measure methane production in seawater samples amended with methylphosphonate, an organic, phosphorus-containing compound. We show that methane is produced aerobically as a by-product of methylphosphonate decomposition in phosphate-stressed waters. Methylphosphonate decomposition, and thus methane production, may be enhanced by the activity of nitrogen-fixing microorganisms. We suggest that aerobic marine methane production will be sensitive to the changes in water-column stratification and nutrient limitation that are likely to result from greenhouse-gas-induced ocean warming.