1. Nutrient enrichment and resulting eutrophication is a widespread anthropogenic influence on freshwater ecosystems, but recovery from nutrient enrichment is poorly understood, especially in stream environments. We examined multi-year patterns in community recovery from experimental low-concentration nutrient enrichment (N + P or P only) in three reaches of two Arctic tundra streams (Kuparuk River and Oksrukuyik Creek) on the North Slope of Alaska (U.S.A.). 2. Rates of recovery varied among community components and depended on duration of enrichment (2-13 consecutive growing seasons). Biomass of epilithic algae returned to reference levels rapidly (within 2 years), regardless of nutrients added or enrichment duration. Aquatic bryophyte cover, which increased greatly in the Kuparuk River only after long-term enrichment (8 years), took 8 years of recovery to approach reference levels, after storms had scoured most remnant moss in the recovering reach. 3. Multi-year persistence of bryophytes in the Kuparuk River appeared to prevent recovery of insect populations that had either been positively (e.g. the mayfly Ephemerella, most chironomid midge taxa) or negatively (e.g. the tube-building chironomid Orthocladius rivulorum) affected by this shift in dominant primary producer. These lags in recovery (of >3 years) were probably driven by the persistent effect of bryophytes on physical benthic habitat. 4. Summer growth rates of Arctic grayling (both adults and young-of-year) in Oksrukuyik Creek (fertilised for 6 years with no bryophyte colonisation), which were consistently increased by nutrient addition, returned to reference rates within 1-2 years. 5. Rates of recovery of these virtually pristine Arctic stream ecosystems from low-level nutrient enrichment appeared to be controlled largely by duration of enrichment, mediated through physical habitat shifts caused by eventual bryophyte colonisation, and subsequent physical disturbance that removed bryophytes. Nutrient enrichment of oligotrophic Arctic stream ecosystems caused by climate change or local anthropogenic activity may have dramatic and persistent consequences if it results in the colonisation of long-lived primary producers that alter physical habitat. ?? 2007 The Authors.