Madagascar’s Central Highlands are largely composed of grasslands, interspersed with patches of forest. The pre-human extent of these grasslands is a topic of vigorous debate, with conventional wisdom holding that they are anthropogenic in nature and emerging evidence supporting that grasslands were a component of the pre-human Central Highlands vegetation. Here, we shed light on the temporal dynamics of Madagascar’s vegetative composition by conducting a population genomic investigation of Goodman’s mouse lemur (Microcebus lehilahytsara; Cheirogaleidae). These small-bodied primates occur both in Madagascar’s eastern rainforests and in the Central Highlands, which makes them a valuable indicator species. Population divergences among forest-dwelling mammals can serve as a proxy for habitat fragmentation and patterns of post-divergence gene flow can reveal potential migration corridors consistent with a wooded grassland mosiac. We used RADseq data to infer phylogenetic relationships, population structure, demographic models of post-divergence gene flow, and population size change through time. These analyses offer evidence that open habitats are an ancient component of the Central Highlands, and that wide-spread forest fragmentation occurred naturally during a period of decreased precipitation near the last glacial maximum. Models of gene flow suggest that migration across the Central Highlands has been possible from the Pleistocene through the recent Holocene via riparian corridors. Notably, though our findings support the hypothesis that Central Highland grasslands predate human arrival, we also find evidence for human-mediated population declines. This highlights the extent to which species imminently threatened by human-mediated deforestation may be more vulnerable from paleoclimatic changes.