Petroleum coke (PC) is a waste by-product generated during the oil upgrading processes by the petroleum industry. The continuing accumulation of large quantities of PC requires the development of innovative strategies for the effective utilization of this carbon-rich material. In this study, PC was used for the removal of naphthenic acids (NAs) and acid-extractable fraction (AEF) from oil sands process-affected water (OSPW), generated during the oil refining process. A systematic study on the adsorption of organic fractions, vanadium leaching from PC, adsorption mechanisms, and the effect of physico-chemical characteristics of the PC on adsorption process was performed. Physico-chemical properties of PC were determined by Fourier transform infrared spectroscopy (FT-IR), X-ray photoelectron spectroscopy, thermogravimetric analysis (TGA), scanning electron microscopy, and Brunauer–Emmett–Teller surface area analysis. AEF and NAs removals of 60 and 75 %, respectively, were achieved at PC dose of 200 g/L after 16 h of contact. FT-IR and TGA analysis of PC suggested the physisorption of organic compounds onto the surface of PC. The calculated mean free energy of adsorption (E < 8 kJ/mol) also indicated the physisorption of organics to the PC surface. The hydrophobic interactions between the NAs and the PC were suggested as the dominant adsorption mechanisms. The vanadium release occurred when PC was mixed with OSPW and vanadium concentration increased with an increase in the PC dose. Speciation analysis indicated that the vanadium leached was predominantly vanadium (V) and insignificant amount of vanadium (IV) was also detected.