A microbial mat from the Black Sea shelf was analyzed by a metagenomic approach. While the habitat and its microbial community are characterized by anaerobic methane oxidation, a 79 kb contiguous DNA sequence obtained from the same mat provided first evidence for the concomitant presence of the capacity for anaerobic benzoate degradation. Benzoyl-CoA is one central intermediate of anaerobic aromatic degradation, among others. Within a stretch of 31 kb, all genes required for the complete pathway of anaerobic benzoate degradation (catabolic island) were identified, including the four subunits of the key enzyme benzoyl-CoA reductase (bcrCBAD), which catalyzes the ATP-driven 2-electron reduction of the aromatic ring. Genes for a ketoacid:acceptor oxidoreductase (korABC) and a ferredoxin (fdx), which are required for generation of a suitable electron donor, were also detected. The majority of the identified catabolic gene products are most similar to their respective orthologs from the denitrifying freshwater bacterium Azoarcus evansii, and the genes are also similarly organized. Due to the lack of established markers, the phylogenetic affiliation of the source organism remains unclear. The presented findings indicate that the metabolic diversity of the Black Sea mat is wider than currently known and that probably other bacteria than those of the methane-oxidizing consortia contribute to aromatic degradation in this anoxic habitat.