Polycyclic aromatic hydrocarbons are ubiquitous persistent pollutants. They may accumulate in sludge during wastewater treatment because of their low biodegradability and their hydrophobic characteristics. Combination of ozonation and anaerobic digestion may be efficient to remove PAHs naturally present in sludge. The objective of this study was to investigate the impact of ozone pre-treatment, with and without surfactant addition, on the anaerobic degradation of 12 PAHs (from low to high molecular weight). Under anaerobic digestion without ozonation pre-treatment, the highest removals were obtained for the lightest PAHs (3-aromatic rings). Ozonation pre-treatment of sludge allowed to increase biodegradability or bioavailability of each PAH, and the PAH removals were well correlated to the PAH solubility. Finally, addition of tyloxapol before sludge ozone pre-treatment had antagonist effects on PAH removal during anaerobic digestion: negative impact on anaerobic ecosystem activity and improvement of PAH bioaccessibility (particularly the PAHs with the highest octanol water partition coefficients).