The widespread contamination of aquatic sediments by polycyclic aromatic hydrocarbons (PAHs) has created a need for cost-effective remediation processes. Many common PAHs are biodegradable, leading to studies investigating the potential of sediment bioremediation. This article reviews several factors that currently complicate the implementation of sediment bioremediation processes: the effect of complex mixtures of contaminants on the rate and extent of degradation observed, the bioavailability of PAHs in sorbed- and nonaqueous-phase, and methods being evaluated to enhance degradation/availability (surfactant-enhanced solubility, nutrient addition, and bioaugmentation).