Madagascar is renowned for the loss of the forested habitat of lemurs and other species endemic to the island. Less well known is that in the highlands, a region often described as an environmental "basket-case" of fire-degraded, eroded grasslands, woody cover has been increasing for decades. Using information derived from publically available high- and medium-resolution satellites, this study characterizes tree cover dynamics in the highlands of Madagascar over the past two decades. Our results reveal heterogeneous patterns of increased tree cover on smallholder farms and village lands, spurred by a mix of endogenous and exogenous forces. The new trees play important roles in rural livelihoods, providing renewable supplies of firewood, charcoal, timber and other products and services, as well as defensible claims to land tenure in the context of a decline in the use of hillside commons for grazing. This study documents this nascent forest transition through Land Change Science techniques, and provides a prologue to political ecological analysis by setting these changes in their social and environmental context and interrogating the costs and benefits of the shift in rural livelihood strategies.