Mantle melting, which leads to the formation of oceanic and continental crust, together with crust recycling through plate tectonics, are the primary processes that drive the chemical differentiation of the silicate Earth. The present-day mantle, as sampled by oceanic basalts, shows large chemical and isotopic variability bounded by a few end-member compositions1. Among these, the HIMU end-member (having a high U/Pb ratio, μ) has been generally considered to represent subducted/recycled basaltic oceanic crust2,3,4,5. However, this concept has been challenged by recent studies of the mantle source of HIMU magmas. For example, analyses of olivine phenocrysts in HIMU lavas indicate derivation from the partial melting of peridotite, rather than from the pyroxenitic remnants of recycled oceanic basalt6. Here we report data that elucidate the source of these lavas: high-precision trace-element analyses of olivine phenocrysts point to peridotite that has been metasomatized by carbonatite fluids. Moreover, similarities in the trace-element patterns of carbonatitic melt inclusions in diamonds7 and HIMU lavas indicate that the metasomatism occurred in the subcontinental lithospheric mantle, fused to the base of the continental crust and isolated from mantle convection. Taking into account evidence from sulfur isotope data8 for Archean to early Proterozoic surface material in the deep HIMU mantle source, a multi-stage evolution is revealed for the HIMU end-member, spanning more than half of Earth's history. Before entrainment in the convecting mantle, storage in a boundary layer, upwelling as a mantle plume and partial melting to become ocean island basalt, the HIMU source formed as Archean-early Proterozoic subduction-related carbonatite-metasomatized subcontinental lithospheric mantle.