Ozonation can degrade toxic naphthenic acids (NAs) in oil sands process-affected water (OSPW), but even after extensive treatment a residual NA fraction remains. Here we hypothesized that mild ozonation would selectively oxidize the most biopersistent NA fraction, thereby accelerating subsequent NA biodegradation and toxicity removal by indigenous microbes. OSPW was ozonated to achieve approximately 50% and 75% NA degradation, and the major ozonation byproducts included oxidized NAs (i.e., hydroxy- or keto-NAs). However, oxidized NAs are already present in untreated OSPW and were shown to be formed during the microbial biodegradation of NAs. Ozonation alone did not affect OSPW toxicity, based on Microtox; however, there was a significant acceleration of toxicity removal in ozonated OSPW following inoculation with native microbes. Furthermore, all residual NAs biodegraded significantly faster in ozonated OSPW. The opposite trend was found for ozonated commercial NAs, which are known to contain no significant biopersistent fraction. Thus, we suggest that ozonation preferentially degraded the most biopersistent OSPW NA fraction, and that ozonation is complementary to the biodegradation capacity of microbial populations in OSPW. The toxicity of ozonated OSPW to higher organisms needs to be assessed, but there is promise that this technique could be applied to accelerate the bioremediation of large volumes of OSPW in Northern Alberta, Canada.