Due to the Benguela Current, the entire Namibian coast is extremely arid with harsh weather conditions. This is especially true for its northern part, the Skeleton Coast. Since their first encounter with this landscape European travellers have perceived it as a hostile and deserted wilderness – a pristine landscape. Archaeological investigations undertaken in neighbouring Kaokoland by the University of Cologne have concentrated on various ecological zones. However, the extreme arid environment of the Namib Desert has not been examined until recently. Our surveys have yielded an unexpected wealth of archaeological sites, which fall into two main categories: shell middens and stone circle sites. Both settlement patterns document the exploitation of marine food resources and attest to a strong connection between the hinterland and the coast. In contrast to rock shelter sites in the interior of northwestern Namibia which are suitable for diachronic charcoal analyses, surface sites in the northern Namib Desert were occupied for only short periods in the late Holocene. During this phase, climatic conditions in the coastal desert most probably resembled those presently prevailing. Anthracological analysis from these sites provides palaeoethnobotanical information on the use of the scarce woody vegetation for fuel. Results generally indicate that even in this hyperarid environment, availability and accessibility were of major importance for firewood choice. However, the anthracological proof of some woody species presently occurring only at some distance from the coastal sites, may indicate mobility of the former inhabitants, fluctuations of ephemeral rivers in the hinterland, or the collection of marine driftwood.