Populations of anatomically archaic (Neandertal) and early modern (Cro-Magnoid) humans are jointly documented in the European fossil record, in the period between 40 000 and 25 000 years BP, but the large differences between their cultures, morphologies and DNAs suggest that the two groups were not close relatives. However, it is still unclear whether any genealogical continuity between them can be ruled out. Here, we simulated a broad range of demographic scenarios by means of a serial coalescence algorithm in which Neandertals, Cro-Magnoids and modern Europeans were either part of the same mitochondrial genealogy or of two separate genealogies. Mutation rates, population sizes, population structure and demographic growth rates varied across simulations. All models in which anatomically modern (that is, Cro-Magnoid and current) Europeans belong to a distinct genealogy performed better than any model in which the three groups were assigned to the same mitochondrial genealogy. The maximum admissible level of gene flow between Neandertals and the ancestors of current Europeans is 0.001% per generation, one order of magnitude lower than estimated in previous studies not considering genetic data on Cro-Magnoid people.