Polycyclic aromatic hydrocarbons (PAHs) are ubiquitous and toxic pollutants in the environment that are mostly introduced through anthropogenic activities. They are very stable with low bioavailability and, because aerobic degradation is mostly limited in aquifers and sediments, often persist in anoxic systems. In this review, we elucidate the recent advances in PAH degradation by anaerobic, mostly sulfate-reducing cultures. The best-studied compound is naphthalene, the smallest and simplest PAH, which often serves as a model compound for anaerobic PAH degradation. In recent years, three-ring PAHs have also shifted into focus, using phenanthrene as a representative compound. Anaerobic degradation of PAHs has to overcome several biochemical problems. First, non-substituted PAHs have to be activated by carboxylation, which is chemically challenging and proposed to involve a 1,3-cycloaddition with a UbiD-like carboxylase and a prenylated flavin cofactor. The second key reaction is to overcome the resonance energy of the ring system, which is performed by consecutive two-electron reduction steps involving novel type III aryl-CoA reductases belonging to the old-yellow enzyme family. In naphthalene degradation, a type I aryl-CoA reductase is also involved in reducing a benzene ring structure. The third key reaction is the ring cleavage, involving beta-oxidation-like reactions in cleaving ring I of naphthalene. Ring II, however, is opened by a novel lyase reaction at a tertiary, hydroxylated carbon atom. These principles are explained using examples of anaerobic naphthalene and phenanthrene degradation to give an overview of recent advances, from the initial activation of the molecules to the complete degradation to CO2.