A batch experiment was conducted to compare PAH degradation in a polluted river sediment under aerobic and anaerobic conditions, and to investigate whether input of fresh organic material (cellulose) could enhance such degradation. All measurements were checked against abiotic control treatments to exclude artifacts of sample preparation and non-biological processes like aging. Three- and four-ring PAHs could be degraded by the indigenous microbial community under aerobic conditions, but anaerobic metabolism based on iron and sulphate reduction was not coupled with PAH degradation of even the simplest 3-ring compounds like phenanthrene. Cellulose addition stimulated both aerobic and anaerobic respiration, but had no effect on PAH dissipation. We conclude that natural attenuation of PAHs in polluted river sediments under anaerobic conditions is exceedingly slow. Dredging and biodegradation on land under aerobic conditions would be required to safely remediate and restore polluted sites.