Bones and teeth are important sources of Pleistocene hominin DNA, but are rarely recovered at archaeological sites. Mitochondrial DNA (mtDNA) has been retrieved from cave sediments but provides limited value for studying population relationships. We therefore developed methods for the enrichment and analysis of nuclear DNA from sediments and applied them to cave deposits in western Europe and southern Siberia dated to between 200,000 and 50,000 years ago. We detected a population replacement in northern Spain about 100,000 years ago, which was accompanied by a turnover of mtDNA. We also identified two radiation events in Neanderthal history during the early part of the Late Pleistocene. Our work lays the ground for studying the population history of ancient hominins from trace amounts of nuclear DNA in sediments.