Using Landsat images acquired since early 1970s, we have mapped the forest cover and change between 1989 and 2000, and estimated forest area in 1973 in Paraguay's Atlantic Forest Ecoregion (PAFE). The results revealed that as of 1973, 73.4% of the PAFE region was covered by forest. Since then, the proportion of forested area was quickly reduced to 40.7% by 1989 and further down to 24.9% by 2000. Two competing deforestation processes contributed to this rapid forest loss, with the first being driven by settlers and the second by large private land owners. During the 1989–2000 period, 80% of deforested areas were cleared by private land owners and 20% by the settlers. Protected areas slowed down forest loss within their boundaries, but not in their surrounding areas. The average percent forest loss in the area within 5 km from the boundary of Paraguay's major forested protected areas was 39% during the 1989–2000 period, which was essentially the same as that for the entire PAFE region during the same period. The high rates of forest loss in the areas surrounding the protected areas not only left the protected areas highly isolated as ecological “islands”, they may also be precursors to rapid forest loss within the protected areas. These protected areas are critical to the conservation of many species endemic or limited to the PAFE region and surrounding areas, and should be continuously monitored using recent and future satellite observations.