Stable isotope probing (SIP) is a cultivation-free methodology that provides information about the identity of microorganisms participating in assimilatory processes in complex communities. In this study, a Herminiimonas-related bacterium was identified as the dominant member of a denitrifying microcosm fed [(13)C]toluene. The genome of the uncultivated toluene-degrading bacterium was obtained by applying pyrosequencing to the heavy DNA fraction. The draft genome comprised ~3.8 Mb, in 131 assembled contigs. Metabolic reconstruction of aromatic hydrocarbon (toluene, benzoate, p-cresol, 4-hydroxybenzoate, phenylacetate, and cyclohexane carboxylate) degradation indicated that the bacterium might specialize in anaerobic hydrocarbon degradation. This characteristic is novel for the order Burkholderiales within the class Betaproteobacteria. Under aerobic conditions, the benzoate oxidation gene cluster (BOX) system is likely involved in the degradation of benzoate via benzoyl coenzyme A. Many putative genes for aromatic hydrocarbon degradation were closely related to those in the Rhodocyclaceae (particularly Aromatoleum aromaticum EbN1) with respect to organization and sequence similarity. Putative mobile genetic elements associated with these catabolic genes were highly abundant, suggesting gene acquisition by Herminiimonas via horizontal gene transfer.