Surface mining of bitumen extraction from Alberta’s oil sands generates large volumes of oil sands process-affected water (OSPW) that is stored in tailings ponds. Naphthenic acids (NAs) are toxic, corrosive, and complex, cyclic carboxylic acids that accumulate in tailings ponds over time and must be removed for effective reclamation. This work has examined microbial NA biodegradation under aerobic and anaerobic conditions as a possible approach for reclamation. Phosphate stimulation of oxic OSPW resulted in growth of algae (Scenedesmus, Chlorella) and bacteria (Porphyrobacter, Planctomyces) capable of biodegrading low molecular weight NAs resulting in small decreases in acute toxicity. Several new NA-biodegrading bacteria were isolated from OSPW and identified. Additionally, this work has now shown that NA can be biodegraded under nitrate-, iron-, sulfate-reducing and methanogenic conditions and has identified microbial community members likely contributing to NA biodegradation. These findings show that the use of microorganisms for NA remediation may be possible.