The process by which the Neanderthals were replaced by modern humans between 42,000 and 30,000 before present is still intriguing. Although no Neanderthal mitochondrial DNA (mtDNA) lineage is found to date among several thousands of Europeans and in seven early modern Europeans, interbreeding rates as high as 25% could not be excluded between the two subspecies. In this study, we introduce a realistic model of the range expansion of early modern humans into Europe, and of their competition and potential admixture with local Neanderthals. Under this scenario, which explicitly models the dynamics of Neanderthals' replacement, we estimate that maximum interbreeding rates between the two populations should have been smaller than 0.1%. We indeed show that the absence of Neanderthal mtDNA sequences in Europe is compatible with at most 120 admixture events between the two populations despite a likely cohabitation time of more than 12,000 y. This extremely low number strongly suggests an almost complete sterility between Neanderthal females and modern human males, implying that the two populations were probably distinct biological species.