Detailed petrography, microstructure, and geochemistry of garnet pyroxenite xenoliths in Holocene basanite tuffs from maars at Lakes Bullenmerri and Gnotuk (western Victoria, southeastern Australia) have been used to track their igneous and metamorphic history, enabling the reconstruction of the thermal-tectonic evolution of the lithospheric mantle. The exsolution of orthopyroxene and garnet and rare spinel, plagioclase, and ilmenite from complex clinopyroxene megacrysts suggests that the xenoliths originally were clinopyroxene-dominant cumulates associated with minor garnet, orthopyroxene, or spinel. The compositions of exsolved phases and their host clinopyroxene were reintegrated using measured modal proportions to show that the primary clinopyroxene was enriched in Al2O3 (5.53-13.63 wt%) and crystallized at ∼1300-1500 °C and 16-30 kbar. These cumulates then underwent extensive exsolution, recrystallization, and reaction during cooling, and finally equilibrated at ∼950-1100 °C and 12-18 kbar before entrainment in the basanites. Rare earth element (REE) thermobarometry of garnets and coexisting clinopyroxenes preserves evidence of an intermediate stage (1032 °C and 21 kbar). These results imply that the proto-liths of the garnet pyroxenite formed at a range of depths from ∼50 to 100 km, and then during or shortly after cooling, they were tectonically emplaced to higher levels (∼40-60 km; i.e., uplifted by at least 10-20 km) along the prevailing geotherm. This uplift may have been connected with lithosphere-scale faulting during the Paleozoic orogeny, or during Mesozoic-Cenozoic rifting of eastern Australia.