The African protected area (PA) network has the potential to act as a set of functionally interconnected patches that conserve meta-populations of mammal species, but individual PAs are vulnerable to habitat change which may disrupt connectivity and increase extinction risk. Individual PAs have different roles inmaintaining connectivity, depending on their size and location. We measured their contribution to network connectivity (irreplaceability) for carnivores and ungulates and combined it with a measure of vulnerability based on a 30-year trend in remotely sensed vegetation cover (Normalized Difference Vegetation Index). Highly irreplaceable PAs occurred mainly in southern and eastern Africa. Vegetation cover change was generally faster outside than inside PAs and particularly so in southernAfrica. The extent of change increased with the distance from PAs. About 5% of highly irreplaceable PAs experienced a faster vegetation cover loss than their surroundings, thus requiring particular conservation attention. Our analysis identified PAs at risk whose isolationwould disrupt the connectivity of the PA network for large mammals. This is an example of how ecological spatial modelling can be combined with large-scale remote sensing data to investigate how land cover change may affect ecological processes and species conservation. © 2014 The Author(s) Published by the Royal Society. All rights reserved.