Methane is a potent greenhouse gas that is produced in significant quantities by aerobic marine organisms. These bacteria apparently catalyse the formation of methane through the cleavage of the highly unreactive carbon-phosphorus bond in methyl phosphonate (MPn), but the biological or terrestrial source of this compound is unclear. However, the ocean-dwelling bacterium Nitrosopumilus maritimus catalyses the biosynthesis of MPn from 2-hydroxyethyl phosphonate and the bacterial C-P lyase complex is known to convert MPn to methane. In addition to MPn, the bacterial C-P lyase complex catalyses C-P bond cleavage of many alkyl phosphonates when the environmental concentration of phosphate is low. PhnJ from the C-P lyase complex catalyses an unprecedented C-P bond cleavage reaction of ribose-1-phosphonate-5-phosphate to methane and ribose-1,2-cyclic-phosphate-5-phosphate. This reaction requires a redox-active [4Fe-4S]-cluster and S-adenosyl-L-methionine, which is reductively cleaved to L-methionine and 5'-deoxyadenosine. Here we show that PhnJ is a novel radical S-adenosyl-L-methionine enzyme that catalyses C-P bond cleavage through the initial formation of a 5'-deoxyadenosyl radical and two protein-based radicals localized at Gly 32 and Cys 272. During this transformation, the pro-R hydrogen from Gly 32 is transferred to the 5'-deoxyadenosyl radical to form 5'-deoxyadenosine and the pro-S hydrogen is transferred to the radical intermediate that ultimately generates methane. A comprehensive reaction mechanism is proposed for cleavage of the C-P bond by the C-P lyase complex that uses a covalent thiophosphate intermediate for methane and phosphate formation.