Polycyclic aromatic hydrocarbons (PAHs) are among the most targeted contaminants by international regulatory institutions. There is thus a need for fast, selective and sensitive analytical methods to quantify these compounds at trace levels in complex samples. This article focuses on the optimization by means of an experimental design of a CE method with laser-induced fluorescence detection for the fast simultaneous separation of 8 heavy PAHs among food and environmental priority pollutants: benzo(a)pyrene, benzo(a)anthracene, chrysene, benzo(b)fluoranthene, dibenzo(a,h)anthracene, indeno(1,2,3-cd)pyrene, benzo(k)fluoranthene, and benzo(ghi)perylene. In this method, capillary zone electrophoresis with a mixture of an anionic sulfobutyl ether-β-cyclodextrin (SBE-β-CD) and a neutral methyl-β-cyclodextrin (Me-β-CD) was used to separate PAHs, on the basis of their differential distribution between the two CDs. First, the factors most affecting PAH electrophoretic behavior were identified: SBE-β-CD and Me-β-CD concentrations and percentage of methanol added to the background electrolyte. Then, a response surface strategy using a central composite design was carried out to model the effects of the selected factors on the normalized migration times. To optimize the separation, desirability functions were applied on modeled responses: normalized migration time differences between peak end and peak start of two consecutive peaks, and overall analysis time. From the model, predicted optimum conditions were experimentally validated and full resolution of all 8 PAHs was achieved in less than 7min using a borate buffer composed of 5.3mM SBE-β-CD, 21.5mM Me-β-CD and 10.3% MeOH. This CE separation method was successfully applied to real edible oil analysis.