Archaeological evidence shows that, in the long run, Neolitization (the transition from foraging to food production) was associated with demographic growth. We used two methods (patterns of linkage disequilibrium from whole-genome SNPs and MSMC estimates on genomes) to reconstruct the demographic profiles for respectively 64 and 24 modern-day populations with contrasting lifestyles across the Old World (sub-Saharan Africa, south-eastern Asia, Siberia). Surprisingly, in all regions, food producers had larger effective population sizes ($Ne$) than foragers already 20k years ago, well before the Neolithic revolution. As expected, this difference further increased ~12–10k years ago, around or just before the onset of food production. Using paleoclimate reconstructions, we show that the early difference in $Ne$ cannot be explained by food producers inhabiting more favorable regions. A number of mechanisms, including ancestral differences in census size, sedentism, exploitation of the natural resources, social stratification or connectivity between groups, might have led to the early differences in Ne detected in our analyses. Irrespective of the specific mechanisms involved, our results provide further evidence that long term cultural differences among populations of Palaeolithic hunter-gatherers are likely to have played an important role in the later Neolithization process.