Several new species of the genus Sphingomonas including S. aromaticivorans, S. stygia, and S. subterranea that have the capacity for degrading a broad range of aromatic compounds including toluene, naphthalene, xylenes, p-cresol, fluorene, biphenyl, and dibenzothiophene, were isolated from deeply-buried (>200 m) sediments of the US Atlantic coastal plain (ACP). In S. aromaticivorans F199, many of the genes involved in the catabolism of these aromatic compounds are encoded on a 184-kb conjugative plasmid; some of the genes involved in aromatic catabolism are plasmid-encoded in the other strains as well. Members of the genus Sphingomonas were common among aerobic heterotrophic bacteria cultured from ACP sediments and have been detected in deep subsurface environments elsewhere. The major source of organic carbon for heterotrophic metabolism in ACP deep aquifers is lignite that originated from plant material buried with the sediments. We speculate that the ability of the subsurface Sphingomonas strains to degrade a wide array of aromatic compounds represents an adaptation for utilization of sedimentary lignite. These and related subsurface Sphingomonas spp may play an important role in the transformation of sedimentary organic carbon in the aerobic and microaerobic regions of the deep aquifers of the ACP.