Public policies can lead to deforestation and forest fragmentation depending on the particular land uses policies seek to promote. In turn, sequences of distinct policy incentives can generate nonlinear trajectories in deforestation and habitat fragmentation. This article takes up the case of Peru, where successive presidential administrations have promoted very different land uses. I focus on Madre de Dios, a frontier region in the southeastern Peruvian Amazon, to evaluate deforestation and fragmentation from 1986 to 2007, which covers several distinct policy periods. I draw on classified Landsat TM, ETM+, and Aster images in 5-year intervals from 1986 to 2001 and bi-annual images from 2001 to 2007 to observe trajectories in forest, crops and pasture, and regrowth. The analysis permits observation of nonlinearities in changes in the land cover classes, as well as fragmentation metrics related to size, density, connectivity, and configuration of the land cover classes over time. Distinct policies show different deforestation trajectories and fragmentation values. These findings bear implications for the study of public policies and spatiotemporal land cover dynamics and offer new monitoring tools to understand the complexity of environmental change.