Termites are landscape geo-engineers whose nesting activities substantially modify the physical and chemical properties of soils. Fossilised termite nests commonly constitute the only identifiable evidence of ancient termite activity and represent valuable trace fossil archives for reconstructing past environments. Here, we describe a new ichnogenus and ichnospecies, Columnanidus calitzdorpensis ichnogen. ichnosp. nov., from Quaternary alluvial deposits near Calitzdorp, South Africa. The subterranean nests are subcylindrical structures, reaching similar to 1 m in height and similar to 65 cm in diameter, and are characterised by a similar to 12 cm wide, shelved nest wall surrounding an empty central cavity. Within the nest wall, the gallery and chamber morphology and abundance vary between the inner and outer zones. The nests are preserved as calcretised features, composed of inter-laminations of clastic sediment and pedogenic carbonate precipitate. U-series dating of the carbonate laminations yields robust age peaks at 401 +/- 46 ka and 323 +/- 12 ka, indicating a Middle Pleistocene minimum age for nest formation. These ages coincide with intervals favourable for pedogenic carbonate development under semi-arid to arid climatic conditions. Hardpan calcretes capping the nests suggest prolonged periods of semi-arid conditions and sustained pedogenic stability during the Middle Pleistocene in the Calitzdorp region.