Coal-bed methane is one of the largest unconventional natural gas resources. Although microbial activity may greatly contribute to coal-bed methane formation, it is unclear whether the complex aromatic organic compounds present in coal can be used for methanogenesis. We show that deep subsurface-derivedMethermicoccusmethanogens can produce methane from more than 30 types of methoxylated aromatic compounds (MACs) as well as from coals containing MACs. In contrast to known methanogenesis pathways involving one- and two-carbon compounds, this “methoxydotrophic” mode of methanogenesis couplesO-demethylation, CO2 reduction, and possibly acetyl-coenzyme A metabolism. Because MACs derived from lignin may occur widely in subsurface sediments, methoxydotrophic methanogenesis would play an important role in the formation of natural gas not limited to coal-bed methane and in the global carbon cycle.