Protected Areas (PAs) in Tanzania had been established originally for the goal of habitat, landscape and biodiversity conservation. However, human activities such as agricultural expansion and wood harvesting pose challenges to the conservation objectives. We monitored a decade of deforestation within 708 PAs and their unprotected buffer areas, analyzed deforestation by PA management regimes, and assessed connectivity among PAs. Data came from a Landsat-based wall-to-wall forest to non-forest change map for the period 2002–2013, developed for the definition of Tanzania’s National Forest Reference Emissions Level (FREL). Deforestation data were extracted in a series of concentric bands that allow pairwise comparison and correlation analysis between the inside of PAs and the external buffer areas. Half of the PAs exhibit either no deforestation or significantly less deforestation than the unprotected buffer areas. A small proportion (10%; n = 71) are responsible for more than 90% of the total deforestation; but these few PAs represent more than 75% of the total area under protection. While about half of the PAs are connected to one or more other PAs, the remaining half, most of which are Forest Reserves, are isolated. Furthermore, deforestation inside isolated PAs is significantly correlated with deforestation in the unprotected buffer areas, suggesting pressure from land-use outside PAs. Management regimes varied in reducing deforestation inside PA territories, but differences in protection status within a management regime are also large. Deforestation as percentages of land area and forested areas of PAs was largest for Forest Reserves and Game Controlled areas, while most National Parks, Nature Reserves and Forest Plantations generally retained large proportions of their forest cover. Areas of immediate management concern include the few PAs with a disproportionately large contribution to the total deforestation and the sizeable number of PAs being isolated. Future protection should account for landscapes outside protected areas, engage local communities and establish new PAs or corridors such as village-managed forest areas.