Zealandia is a largely submerged, continental fragment in the southwest Pacific, generally considered to be derived from East Gondwana, but whose origins, age, structure, and relationships with other continental masses are poorly known. To explore the development of this microcontinent, a suite of mantle xenoliths was assembled from 12 localities throughout New Zealand, an emergent part of Zealandia. The 187Re-188Os isotopic systematics of the xenoliths yield model ages (TRD2) between 0 and 2.3 Ga. Six samples from the newly defined Waitaha domain, South Island, have a narrow range of TRD2 ages from 1.6 to 1.9 Ga, in agreement with an aluminochron model age for this mantle domain of ca. 1.95 Ga, and with a three-point Re-Os isochron age of 2.26 ± 0.10 Ga. These ages are >500 m.y. older than TRD2 ages preserved in other regions of mantle lithosphere from the eastern margin of Gondwana (e.g., southeastern Australia and Marie Byrd Land, Antarctica) and >1 b.y. older than the oldest crustal rocks exposed in New Zealand. Thus, the lithospheric mantle of Zealandia has a complex age structure, including a region of Paleoproterozoic cratonic mantle with a minimum extent of ~45,000 km2. This ancient mantle resided at the margins of several supercontinents during the past ~2 b.y., attesting to the durability of subcontinental lithospheric mantle domains, even when decoupled from overlying contemporaneous crust and in an oceanic setting distanced from stable cratonic nuclei.