The main goal of this study was to use an oleophilic biostimulant (S-200) to target possible nutritional limitations for biodegradation of polycyclic aromatic hydrocarbons (PAHs) at the interface between nonaqueous-phase liquids (NAPLs) and the water phase. Biodegradation of PAHs present in fuel-containing NAPLs was slow and followed zero-order kinetics, indicating bioavailability restrictions. The biostimulant enhanced the biodegradation, producing logistic (S-shaped) kinetics and 10-fold increases in the rate of mineralization of phenanthrene, fluoranthene, and pyrene. Chemical analysis of residual fuel oil also evidenced an enhanced biodegradation of the alkyl-PAHs and n-alkanes. The enhancement was not the result of an increase in the rate of partitioning of PAHs into the aqueous phase, nor was it caused by the compensation of any nutritional deficiency in the medium. We suggest that biodegradation of PAH by bacteria attached to NAPLs can be limited by nutrient availability due to the simultaneous consumption of NAPL components, but this limitation can be overcome by interface fertilization.