Tailings pond water produced from the extraction of bitumen from the oil sands in Northern Alberta, Canada, was treated using the spray freezing process. The wastewater was frozen by spraying at −10◦C and −24◦C ambient temperatures. The effect of the degree of freezing (i.e., freezing with and without runoff generation) of the sprayed water on the treatment efficiency, the concentration, and distribution of the impurities within the ice columns was examined. When the sprayed water only partially froze (i.e., freezing with runoff formation), the treatment efficiency (measured by reduction in COD, TOC, conductivity, Cl−, SO 2− concentrations) was higher and larger volumes of high quality 4 meltwater was obtained. Reduction of toxicity (Microtox) in meltwater, and the relationship between the overall impurity removal and toxicity reduction was also examined in this study. The decay coefficients were determined for prediction of meltwater impurity concentrations using mathematical models.