Due to the hydrophobic nature of the polyaromatic hydrocarbons (PAHs) they are mostly bound to the sludge and escape aerobic treatment in a wastewater treatment plant. They therefore proceed directly to the anaerobic post treatment, terminate in the sludge, and can be released to the environment if land spreading is used. PAH degradation in anaerobic methanogenic systems has only recently been shown to occur. In this study we have assessed several factors of anaerobic PAH degradation by evaluating thermodynamic feasibility of degradation, assessing degradation at different temperatures, and investigating the enriched cultures using fluorescent in-situ hybridization (FISH). Thermodynamic calculations indicated that PAH degradation was possible under methanogenic conditions, in the presence of hydrogen utilizing methanogens. Removal of naphthalene and 1-methyl naphthalene depended both on temperature and the initial inoculum. Inocula sourced from contaminated land sites were the most effective. The enrichments were all a mixture of Bacteria, and Archaea, and the Archaea were generally identified as Methanobacteriales, using an order-specific probe. The bacteria were not specifically identified. The results indicate a syntrophic culture, with the bacteria oxidizing the naphthalene, and the Archaea converting the hydrogen produced by oxidation, to methane.