The replacement of Neanderthals by Anatomically Modern Humans has typically been attributed to environmental pressure or a superiority of modern humans with respect to competition for resources. Here we present two independent models that suggest that no such heatedly debated factors might be needed to account for the demise of Neanderthals. Starting from the observation that Neanderthal populations already were small before the arrival of modern humans, the models implement three factors that conservation biology identifies as critical for a small population's persistence, namely inbreeding, Allee effects and stochasticity. Our results indicate that the disappearance of Neanderthals might have resided in the smallness of their population(s) alone: even if they had been identical to modern humans in their cognitive, social and cultural traits, and even in the absence of inter-specific competition, Neanderthals faced a considerable risk of extinction. Furthermore, we suggest that if modern humans contributed to the demise of Neanderthals, that contribution might have had nothing to do with resource competition, but rather with how the incoming populations geographically restructured the resident populations, in a way that reinforced Allee effects, and the effects of inbreeding and stochasticity.