In this study we investigate Pleistocene vegetation and climate change in southern East Africa by examining plant leaf waxes in a marine sediment core that receives terrestrial runoff from the Limpopo River. The plant leaf wax records are compared to a multi-proxy sea surface temperature (SST) record and pollen assemblage data from the same site. We find that Indian Ocean SST variability, driven by high-latitude obliquity, exerted a strong control on the vegetation of southern East Africa during the past 800,000 yr. Interglacial periods were characterized by relatively wetter and warmer conditions, increased contributions of C3 vegetation, and higher SST, whereas glacial periods were marked by cooler and arid conditions, increased contributions of C4 vegetation, and lower SST. We find that Marine Isotope Stages (MIS) 5e, 11c, 15e and 7a–7c are strongly expressed in the plant leaf wax records but MIS 7e is absent while MIS 9 is rather weak. Our plant leaf wax records also record the climate transition associated with the Mid-Brunhes Event (MBE) suggesting that the pre-MBE interval (430–800 ka) was characterized by higher inputs from grasses in comparison to relatively higher inputs from trees in the post-MBE interval (430 to 0 ka). Differences in vegetation and SST of southern East Africa between the pre- and post-MBE intervals appear to be related to shifts in the location of the Subtropical Front. Comparison with vegetation records from tropical East Africa indicates that the vegetation of southern East Africa, while exhibiting glacial–interglacial variability and notable differences between the pre- and post-MBE portions of the record, likely did not experience such dramatic extremes as occurred to the north at Lake Malawi.