Biogenic methane in subsurface coal seam environments is produced by diverse consortia of microbes. Although this methane is useful for global energy security, it remains unclear which microbes can liberate carbon from the coal. Most of this carbon is relatively resistant to biodegradation, as it is contained within aromatic rings. Thus, to explore for coal-degrading taxa in the subsurface, this study reconstructed relevant metagenome-assembled genomes (MAGs) from coal seams by using a key genomic marker for the anaerobic degradation of monoaromatic compounds as a guide: the benzoyl-CoA reductase gene (bcrABCD). Three MAGs were identified with this genetic potential. The first represented a novel taxon from the Krumholzibacteriota phylum, which this study is the first to describe. This Krumholzibacteriota MAG contained a full set of genes for benzoyl-CoA dearomatization, in addition to other genes for anaerobic catabolism of monoaromatics. Analysis of Krumholzibacteriota MAGs from other environments revealed that this genetic potential may be common, and thus, Krumholzibacteriota may be important organisms for the liberation of recalcitrant carbon in a broad range of environments. Moreover, the assembly and characterization of two Syntrophorhabdus aromaticivorans MAGs from different continents and a Syntrophaceae sp. MAG implicate the Deltaproteobacteria class in coal seam monoaromatic degradation. Each of these taxa are potential rate-limiting organisms for subsurface coal-to-methane biodegradation. Their description here provides some understanding of their function within the coal seam microbiome and will help inform future efforts in coal bed methane stimulation, anoxic bioremediation of organic pollutants, and assessments of anoxic, subsurface carbon cycling and emissions.