The recovery of DNA sequences from early modern humans (EMHs) could shed light on their interactions with archaic groups such as Neandertals and their relationships to current human populations. However, such experiments are highly problematic because present-day human DNA frequently contaminates bones [1, 2]. For example, in a recent study of mitochondrial (mt) DNA from Neolithic European skeletons, sequence variants were only taken as authentic if they were absent or rare in the present population, whereas others had to be discounted as possible contamination [3, 4]. This limits analysis to EMH individuals carrying rare sequences and thus yields a biased view of the ancient gene pool. Other approaches of identifying contaminating DNA, such as genotyping all individuals who have come into contact with a sample, restrict analyses to specimens where this is possible [5, 6] and do not exclude all possible sources of contamination. By studying mtDNA in Neandertal remains, where contamination and endogenous DNA can be distinguished by sequence, we show that fragmentation patterns and nucleotide misincorporations can be used to gauge authenticity of ancient DNA sequences. We use these features to determine a complete mtDNA sequence from a approximately 30,000-year-old EMH from the Kostenki 14 site in Russia.