Nelson Bay Cave is located on the Robberg Peninsula (34°06′ S, 23°24′ E) at Plettenberg Bay, Cape Province, South Africa. Excavation of the Late Quaternary fill of the cave has provided a rich assemblage of mammalian remains dated between ca. 18,000 and 5000 radiocarbon years B.P. Identification and analysis of these remains has shown that important changes in the composition of the mammalian fauna took place first about 12,000 B.P. and again about 9000 B.P. The earlier change is especially clear-cut and is interpreted to reflect the disappearance of grassland from the area as well as the influence of rising sea level. Both faunal changes were accompanied by changes in associated artifactual materials and it is suggested that faunal and cultural changes were causally linked. The mammalian species dated between 18,000 and 12,000 B.P. include the latest recorded Sub-Saharan occurrences of some extinct taxa and indicate that terminal Pleistocene/Early Holocene megafaunal extinctions may have been more important in Southern Africa than has hitherto been thought.