The impacts of exotic plant species on ecosystem processes are well established, motivating numerous efforts to facilitate native-species recovery. Nonetheless, how the return of native species influences ecosystem processes and how these changes feed back to influence the recovery process are poorly understood. We examined these questions in exotic annual grasslands on Santa Cruz Island, California, USA, where the removal of nonnative herbivores has led to the recovery of the native shrubs Artemisia californica and Eriogonum arborescens. To examine the influence of shrub colonization on nutrient cycling, and the mechanisms by which these changes arise, we measured available nitrogen and phosphorus, and quantified nitrogen mineralization and litterfall rates under shrubs and grasses in the field and in experimental monoculture plots. Both native shrubs altered nitrogen cycling as they colonized the grassland, but they did so in opposite directions. Eriogonum depressed nitrogen pools and mineralization rates via large inputs of nitrogen-poor litter. In contrast Artemisia increased nitrogen and phosphorus pools and nitrogen mineralization rates. Last, to determine if shrub effects on soils favor shrubs or grasses, we conducted a nitrogen and phosphorus fertilization experiment in the field. Only the exotic grass was significantly limited by nitrogen. Thus the depressed nitrogen availability associated with Eriogonum colonization is more harmful to exotic grasses than to the native shrub. By contrast, the elevated nitrogen associated with recovering Artemisia favors grasses over the shrub, possibly hindering recovery of the native. Mechanistic studies of the ecosystem ,impacts of native-plant recovery are useful for managers wishing to predict which native species return ecosystem function, and whether such changes feed back to influence native recovery.