Demographic changes are known to leave footprints on genetic polymorphism. Together with the increased availability of large polymorphism data sets, coalescent-based methods allow inferring the past demography of populations from their present-day patterns of genetic diversity. Here, we analyzed both nuclear (20 noncoding regions) and mitochondrial (HVS-I) resequencing data to infer the demographic history of 66 African and Eurasian human populations presenting contrasting lifestyles (nomadic hunter-gatherers, nomadic herders, and sedentary farmers). This allowed us to investigate the relationship between lifestyle and demography and to address the long-standing debate about the chronology of demographic expansions and the Neolithic transition. In Africa, we inferred expansion events for farmers, but constant population sizes or contraction events for hunter-gatherers. In Eurasia, we inferred higher expansion rates for farmers than herders with HVS-I data, except in Central Asia and Korea. Although isolation and admixture processes could have impacted our demographic inferences, these processes alone seem unlikely to explain the contrasted demographic histories inferred in populations with different lifestyles. The small expansion rates or constant population sizes inferred for herders and hunter-gatherers may thus result from constraints linked to nomadism. However, autosomal data revealed contraction events for two sedentary populations in Eurasia, which may be caused by founder effects. Finally, the inferred expansions likely predated the emergence of agriculture and herding. This suggests that human populations could have started to expand in Paleolithic times, and that strong Paleolithic expansions in some populations may have ultimately favored their shift toward agriculture during the Neolithic.