Geochemical and Re-Os isotopic data for refractory spinel peridotite xenoliths from the Newer Volcanics Province of western Victoria demonstrate that parts of the subcontinental lithospheric mantle (SCLM) beneath southeastern Australia underwent melt depletion during the Late Proterozoic as well as the early Paleozoic. Late Proterozoic Re-Os model ages (as old as 900 Ma) for refractory harzburgites are significantly older than the exposed Cambrian crust. In addition, our Re-Os melt-depletion mantle model ages (TMA) are consistent with Sm-Nd depleted-mantle model ages (TDM) and older zircon U-Pb ages for I-type granites from southeastern Australia, suggesting that this region is underlain by Proterozoic continental lithosphere. In contrast, a fertile spinel lherzolite xenolith has a radiogenic Os isotopic composition (γOs > +8) consistent with derivation from an “enriched-mantle” volume within the SCLM. Ancient subduction of Re-rich oceanic crust or melt metasomatism of the lithospheric mantle may have generated enriched-mantle volumes similar to those sampled by some ocean-island basalts (OIB) and komatiites.