Background Monitoring land change at multiple spatial scales is essential for identifying hotspots of change, and for developing and implementing policies for conserving biodiversity and habitats. In the high diversity country of Colombia, these types of analyses are difficult because there is no consistent wall-to-wall, multi-temporal dataset for land-use and land-cover change. Methodology/Principal Findings To address this problem, we mapped annual land-use and land-cover from 2001 to 2010 in Colombia using MODIS (250 m) products coupled with reference data from high spatial resolution imagery (QuickBird) in Google Earth. We used QuickBird imagery to visually interpret percent cover of eight land cover classes used for classifier training and accuracy assessment. Based on these maps we evaluated land cover change at four spatial scales country, biome, ecoregion, and municipality. Of the 1,117 municipalities, 820 had a net gain in woody vegetation (28,092 km2) while 264 had a net loss (11,129 km2), which resulted in a net gain of 16,963 km2 in woody vegetation at the national scale. Woody regrowth mainly occurred in areas previously classified as mixed woody/plantation rather than agriculture/herbaceous. The majority of this gain occurred in the Moist Forest biome, within the montane forest ecoregions, while the greatest loss of woody vegetation occurred in the Llanos and Apure-Villavicencio ecoregions. Conclusions The unexpected forest recovery trend, particularly in the Andes, provides an opportunity to expand current protected areas and to promote habitat connectivity. Furthermore, ecoregions with intense land conversion (e.g. Northern Andean Páramo) and ecoregions under-represented in the protected area network (e.g. Llanos, Apure-Villavicencio Dry forest, and Magdalena-Urabá Moist forest ecoregions) should be considered for new protected areas.