Dinoflagellate cyst and pollen records from marine sediments off the southwestern African coast reveal three major aridification periods since the last glaciation and an environmental correlation between land and sea. Abundant pollen of desert, semi-desert, and temperate plants 21,000–17,500 cal yr B.P. show arid and cold conditions in southwestern Africa that correspond to low sea surface temperatures and enhanced upwelling shown by dinoflagellate cysts. Occurrence of Restionaceae in the pollen record suggests northward movement of the winter-rain regime that influenced the study area during the last glacial maximum. Decline of Asteroideae, Restionaceae, and Ericaceae in the pollen record shows that temperate vegetation migrated out of the study area about 17,500 cal yr B.P., probably because of warming during the last deglaciation. The warming in southwestern Africa was associated with weakened upwelling and increased sea surface temperatures, 2000–2800 years earlier than in the Northern Hemisphere. Aridification 14,300–12,600 cal yr B.P. is characterized by a prominent increase of desert and semi-desert pollen without the return of temperate vegetation. This aridification corresponds to enhanced upwelling off Namibia and cooler temperatures in Antarctica, and it might have been influenced by oceanic thermohaline circulation. Aridification 11,000–8900 cal yr B.P. is out of phase with the northern African climate. Reduction of the water vapor supply in southwestern Africa at that time may be related to northward excursions of the Intertropical Convergence Zone.