Reports of biogenic methane (CH4) synthesis associated with a range of organisms have steadily accumulated in the literature. This has not happened without controversy and in most cases the process is poorly understood at the gene and enzyme levels. In marine and freshwater environments, CH4 supersaturation of oxic surface waters has been termed the “methane paradox” because biological CH4 synthesis is viewed to be a strictly anaerobic process carried out by O2-sensitive methanogens. Interest in this phenomenon has surged within the past decade because of the importance of understanding sources and sinks of this potent greenhouse gas. In our work on Yellowstone Lake in Yellowstone National Park, we demonstrate microbiological conversion of methylamine to CH4 and isolate and characterize an Acidovorax sp. capable of this activity. Furthermore, we identify and clone a gene critical to this process (encodes pyridoxylamine phosphate-dependent aspartate aminotransferase) and demonstrate that this property can be transferred to Escherichia coli with this gene and will occur as a purified enzyme. This previously unrecognized process sheds light on environmental cycling of CH4, suggesting that O2-insensitive, ecologically relevant aerobic CH4 synthesis is likely of widespread distribution in the environment and should be considered in CH4 modeling efforts.