Olivine is one of the most important minerals used to reconstruct magmatic processes, yet the rare earth element (REE) systematics of Fe-rich olivine in igneous rocks and ore deposits is poorly understood. As detected by in situ laser ablation–inductively coupled plasma–mass spectrometry (LA-ICP-MS) analysis, cumulate fayalite (Fe2SiO4) in the Paleoproterozoic Vergenoeg F-Fe-REE deposit of the Bushveld large igneous province (LIP) in South Africa contains the highest heavy REE (HREE) contents ever recorded for olivine, with HREE enrichment of as much as 6000× chondritic values. Atom probe tomography maps confirm the incorporation of the HREEs into the fayalite crystal lattice, facilitated by lithium acting as a main charge balancer and by high REE contents in the highly fractionated felsic parental melt that is related to the Bushveld LIP. The high HREE concentrations of fayalite in concert with its high modal abundance (>95 vol%) indicate that the fayalite cumulates are the main host for the HREE mineralization of the Vergenoeg deposit. Fayalites of Vergenoeg demonstrate that Fe-rich olivine may fractionate large amounts of HREEs, and we propose fayalite cumulates as potential future targets for HREE exploration.