High Andean forests are biodiversity hotspots that also play key roles in the provisioning of vital ecosystem services for neighboring cities. In past centuries, the hinterland of Andean fast-growing cities often experienced a dramatic decline in forested areas, but there are reports that forest cover has been recovering recently. We analyzed aerial imagery spanning the years 1940 to 2007 from nine administrative localities in the Eastern Andean Cordillera of Colombia in order to elucidate precise patterns of forest vegetation change. To this aim, we performed image object-based classification by means of texture analysis and image segmentation. We then derived connectivity metrics to investigate whether forest cover trajectories showed an increase or decrease in fragmentation and landscape degradation. We observed a forest cover recovery in all the examined localities, except one. In general, forest recovery was accompanied by an increase in core habitat areas. The time scale of the positive trends identified partially coincides with the creation of protected areas in the region, which very likely furthered the recovery of forest patches. This study unveils the long-term dynamics of peri-urban high Andean forest cover, providing valuable information on historical vegetation changes in a highly dynamic landscape.