Large volumes of toxic aqueous tailings containing a complex mixture of naphthenic acids (NAs; CnH2n+ZO2) are produced in northern Alberta by the oil sands industry. Because of their persistence and contribution to toxicity, there is an urgent need to understand the fate of NAs under a variety of remediation scenarios. In a previous study, we developed a highly specific HPLC-high resolution mass spectrometry method for the analysis of NAs. Here we apply this method to determine quantitative structure-persistence relationships and kinetics for commercial NAs and NAs in oil sands process water (OSPW) during aerobic microbial biodegradation. Biodegradation of commercial NAs revealed thatthe mixture contained a substantial labile fraction, which was rapidly biodegraded, and a recalcitrant fraction composed of highly branched compounds. Conversely, NAs in OSPW were predominantly recalcitrant, and degraded slowly by first-order kinetics. Carbon number (n) had little effect on the rate of biodegradation, whereas a general structure-persistence relationship was observed indicating that increased cyclization (Z) decreased the biodegradation rate for NAs in both mixtures. Time to 50% biodegradation ranged from 1 to 8 days among all NAs in the commercial mixture, whereas half-lives for OSPW NAs ranged from 44 to 240 days, likely a result of relatively high alkyl branching among OSPW NAs. It is anticipated that these data will facilitate development of strategic solutions for remediating billions of cubic meters of OSPW stored, or predicted to be generated, in Northern Alberta.