This study investigated the anaerobic degradation of the polycyclic aromatic hydrocarbons (PAHs) phenanthrene and pyrene in mangrove sediment from Taiwan. The anaerobic degradation of PAH was enhanced by the addition of acetate, lactate, pyruvate, sodium chloride, cellulose, or zero-valent iron. However, it was inhibited by the addition of humic acid, di-(2-ethylhexyl) phthalate (DEHP), nonylphenol, or heavy metals. Of the microorganism strains isolated from the sediment samples, we found that strain MSA3 (Clostridium pascui), expressed the best ability to biodegrade PAH. The inoculation of sediment with the strain MSA3 could enhance PAH degradation.