Anaerobic degradation is a key process in many environments either naturally or anthropogenically exposed to petroleum hydrocarbons. Considerable advances into the biochemistry and physiology of selected anaerobic degraders have been achieved over the last decades, especially for the degradation of aromatic hydrocarbons. However, researchers have only recently begun to explore the ecology of complex anaerobic hydrocarbon degrader communities directly in their natural habitats, as well as in complex laboratory systems using tools of molecular biology. These approaches have mainly been facilitated by the establishment of a suite of targeted marker gene assays, allowing for rapid and directed insights into the diversity as well as the identity of intrinsic degrader populations and degradation potentials established at hydrocarbon-impacted sites. These are based on genes encoding either peripheral or central key enzymes in aromatic compound breakdown, such as fumarate-adding benzylsuccinate synthases or dearomatizing aryl-coenzyme A reductases, or on aromatic ring-cleaving hydrolases. Here, we review recent advances in this field, explain the different detection methodologies applied, and discuss how the detection of site-specific catabolic gene markers has improved the understanding of processes at contaminated sites. Functional marker gene-based strategies may be vital for the development of a more elaborate population-based assessment and prediction of aromatic degradation potentials in hydrocarbon-impacted environments.