Waterfall Bluff, in Eastern Mpondoland (Eastern Cape Province, South Africa), is a recently excavated archaeological site with deposits spanning Marine Isotope Stage (MIS) 3 to the Middle Holocene. Here, we present preliminary results of a multi-proxy palaeoenvironmental study combining macro-botanical remains, charcoal, phytoliths, pollen and plant waxes derived from the same archaeological record. We aim to understand the interactions between hunter-gatherer plant foraging and climate and environmental change in coastal Mpondoland from MIS 3 to the Early Holocene at Waterfall Bluff. The charcoal and pollen records at Waterfall Bluff show the gathering of a variety of woody taxa characterised by their combustion and medicinal properties (e.g., Millettia grandis and Apodytes dimidiate). The leaves identified in the macrobotanics and in the phytolith record might belong to some of these taxa and it is likely that they were used for medicinal purposes. From a palaeoenvironmental perspective, our results indicate low precipitation and low rainfall seasonality under cool conditions during MIS 3 and the Last Glacial Maximum (LGM). Under these conditions, open woodlands interspersed with dry and hygrophilous grasslands and bushveld vegetation with significant representation of fynbos elements occurred in the local landscapes probably along Podocarpus/Afrocarpus forests. The latter could have been (1) present along river valleys and scarps on the Mpondoland exposed continental shelf towards the south and west of Waterfall Bluff, supported by palaeorivers and cool temperatures favouring low evapotranspiration, or (2) present in the interior with pollen grains possibly transported to the site by intensified westerly winds. These forests contracted as a result of the post-glacial marine transgression or reduced westerlies following the LGM. During the Early Holocene, the palaeoenvironmental signal points to higher summer rainfall and higher seasonality than during MIS 3, the LGM and the LGIT. These changes are coeval with an increase of coastal forests and C4 mesic grasslands with localized wetland vegetation around Waterfall Bluff. These multi-proxy archaeobotanical and biochemical data show that landscapes surrounding Waterfall Bluff changed in relation to marine transgressions/regressions and changes in rainfall intensity and seasonality. The people of Waterfall Bluff foraged the coasts during glacial periods to collect wood.