The loss of forests along with the various types of shrubs in the Mediterranean region is seen as an important driver of climate change and has been repeatedly related with the observed land degradation and desertification in the region. Nevertheless, the extent of woody perennial vegetation cover (WPVC) and its density remain largely unclear. Here, we apply a series of algorithms and methods operationally used in Australia for large-scale WPVC mapping and monitoring and demonstrate their applicability in the Mediterranean region using a Spanish area as the trial site. Five Landsat TM and ETM+ images from various dates spanning 14 years are used to map changes in the extent of WPVC and to identify areas with a declining, stabilising or recovering trend. Results show that the applied methodology, which incorporates (i) preprocessing of the Landsat imagery, (ii) a canonical variate analysis to spectrally discriminate between woody and non-woody land cover types, (iii) a conditional probability network and (iv) spectral indices for mapping woody cover and density trend, is highly successful and well suited for use in Mediterranean environments. A rigorous accuracy assessment is undertaken producing overall accuracies above 97% for both woody and non-woody cover types and all dates. Results also show that in the area of study, the majority of WPVC disturbances were due to forest fires, which represent the region's most frequent natural and anthropogenic disturbance. This raises significant concerns about the future of the area's WPVC. Regeneration compensated to some degree for the high disturbance rates. Copyright © 2015 John Wiley & Sons, Ltd.