The retrieval of mitochondrial DNA (mtDNA) sequences from four Neandertal fossils from Germany, Russia, and Croatia has demonstrated that these individuals carried closely related mtDNAs that are not found among current humans. However, these results do not definitively resolve the question of a possible Neandertal contribution to the gene pool of modern humans since such a contribution might have been erased by genetic drift or by the continuous influx of modern human DNA into the Neandertal gene pool. A further concern is that if some Neandertals carried mtDNA sequences similar to contemporaneous humans, such sequences may be erroneously regarded as modern contaminations when retrieved from fossils. Here we address these issues by the analysis of 24 Neandertal and 40 early modern human remains. The biomolecular preservation of four Neandertals and of five early modern humans was good enough to suggest the preservation of DNA. All four Neandertals yielded mtDNA sequences similar to those previously determined from Neandertal individuals, whereas none of the five early modern humans contained such mtDNA sequences. In combination with current mtDNA data, this excludes any large genetic contribution by Neandertals to early modern humans, but does not rule out the possibility of a smaller contribution.