The relative effect of past climate fluctuations and anthropogenic activities on current biome distribution is subject to increasing attention, notably in biodiversity hot spots. In Madagascar, where humans arrived in the last ~4 to 5,000 years, the exact causes of the demise of large vertebrates that cohabited with humans are yet unclear. The prevailing narrative holds that Madagascar was covered with forest before human arrival and that the expansion of grasslands was the result of human-driven deforestation. However, recent studies have shown that vegetation and fauna structure substantially fluctuated during the Holocene. Here, we study the Holocene history of habitat fragmentation in the north of Madagascar using a population genetics approach. To do so, we infer the demographic history of two northern Madagascar neighbouring, congeneric and critically endangered forest dwelling lemur species—Propithecus tattersalli and Propithecus perrieri—using population genetic analyses. Our results highlight the necessity to consider population structure and changes in connectivity in demographic history inferences. We show that both species underwent demographic fluctuations which most likely occurred after the mid-Holocene transition. While mid-Holocene climate change probably triggered major demographic changes in the two lemur species range and connectivity, human settlements that expanded over the last four millennia in northern Madagascar likely played a role in the loss and fragmentation of the forest cover.