Widespread damage to vegetation on an isolated oceanic island (Macquarie Island), due to overgrazing (since 2002) by an expanding exotic rabbit population, could affect the nature of catchment runoff and result in changes to stream habitats and the composition of their invertebrate communities. To test this hypothesis, stream invertebrate communities that had been sampled originally in 1992 (at 15 sites when rabbit numbers were historically low), were re-sampled in 2008 (17 sites) and in 2010 (12 sites). The number of taxa recorded at each site was 25–36% lower in 2008 (7.4 taxa per site) and in 2010 (8.7 taxa) than in 1992 (11.6 taxa) and an abundance index showed a substantial decline across most taxa. Ordination indicated that composition at all sites changed markedly between years. The greatest compositional changes occurred at sites exposed to moderate or severe levels of vegetation damage, suggesting that stream invertebrates responded to habitat changes associated with increased grazing. An altered input of organic material into the streams as a result of vegetation damage may have been responsible. If communities of stream invertebrates on isolated islands are degraded, then composition may be altered permanently, unless refuges are available.