For most of the past century, prehistorians have had to rely on the fossil and archaeological records in order to reconstruct the past. In the last few decades, this evidence has been substantially supplemented from classical human genetics. More recently, phylogenetic analyses of DNA sequences that incorporate geographical information have provided a high-resolution tool for the investigation of prehistoric demographic events, such as founder effects and population expansions. These events can be dated using a molecular clock when the mutation rate and founder haplotypes are known. We have previously applied such methods to sequence data from the mitochondrial DNA control region, to suggest that most extant mitochondrial sequences in western Europe have a local ancestry in the Early Upper Palaeolithic, with a smaller proportion arriving from the Near East in the Neolithic. Here, we describe a cladistic notation for mitochondrial variation and expand upon our earlier analysis to present a more detailed portrait of the European mitochondrial record.