This study evaluated the potential of ultrasonic enhanced Fenton-based advanced oxidation to reduce toxicity, total phenol (TPh) and organic matter (COD) from olive mill wastewater (OMW). Emphasis was also placed on suggesting a sustainable treatment strategy in the light of accumulated scientific evidence, indicating the role of Fenton-based oxidation in the suggested scheme. Fenton oxidation and Fenton-like oxidation (with Fe2+ and Fe3+) were tested as selected advanced oxidation methods. The experiments were conducted in such a way that the individual removal efficiencies of ultrasonication and advanced oxidation processes be evaluated separately and in sequence. The impact on toxicity removal was tested by means of a standard respirometric method, also currently used to assess biodegradation in wastewaters. Response Surface Methodology (RSM) involving central composite design (CCD) was implemented to assess the optimum conditions. Results highlighted the merit of Fenton-based oxidation with an 80% TPh reduction and a decrease of toxicity down to the narrow margin of 13-17%, together with a COD reduction of 20-26%, all quite meaningful for the following step of biological treatment. The ultrasonic pretreatment also proved to be quite useful as it secured up to 40% of particulate COD dissolution. Studies on particle size distribution of the OMW clearly showed that preliminary treatment including advanced oxidation would leave behind the bulk of soluble COD accumulated below the size of 3 nm. Accordingly, co-treatment of OMW diluted with municipal sewage was recommended after a pretreatment sequence of holding/plain settling; chemical treatment and Fenton-based oxidation. For OMWs with low particulate COD (VSS) content, Fenton-based oxidation enhanced by ultrasonic pretreatment would be a viable option in the view of effective particulate COD dissolution achieved in this study when coupled with ultrafiltration, prior to joint biological treatment with sewage. The study highlighted advanced oxidation as an indispensable step in the treatment of olive mill wastewaters.