Well-preserved and dateable faunal middens in rock shelters of dry areas in southern Africa occur as desiccated urine-rich masses. Under local conditions, which exclude microbial decomposition and oxidation, urine cements together faecal pellets and other inclusions. Nine radiocarbon dated hyrax (Procavia capensis) dung middens from the Kuiseb River Basin of the Namib Desert were sub-sampled and analysed for fossil pollen. Some contain small proportions of rat droppings, but not many macro-fossils. Comparative modern pollen in faecal samples were also studied. Most plant macro-fossils are severely digested, but seeds are well-preserved. Some insect inclusions were identified. Small scale changes in vegetation over the last two millennia were observed, representing environmental fluctuations in cycles of ca. 100-200 years. The fluctuations partly agree with other palynological data from southern Africa and with geomorphologic evidence for environmental changes in the desert region.