Remarkably little is known about the population-level processes leading up to the extinction of the neandertal. To examine this, we use mitochondrial DNA sequences from 13 neandertal individuals, including a novel sequence from northern Spain, to examine neandertal demographic history. Our analyses indicate that recent western European neandertals (<48 kyr) constitute a tightly defined group with low mitochondrial genetic variation in comparison with both eastern and older (>48 kyr) European neandertals. Using control region sequences, Bayesian demographic simulations provide higher support for a model of population fragmentation followed by separate demographic trajectories in subpopulations over a null model of a single stable population. The most parsimonious explanation for these results is that of a population turnover in western Europe during early Marine Isotope Stage 3, predating the arrival of anatomically modern humans in the region.