We used a long-term herbivore removal experiment where paired exclosure-open treatments were established at the Mpala Research Centre, Laikipia, Kenya, in 1999 to examine changes in soil nitrogen (N) at nutrient-rich glades and adjacent nutrient-poor bushland sites after almost two decades of herbivore removal. Glades in this landscape are created by large inputs of dung and urine from previous long-term corralling of cattle in an otherwise nutrient-poor matrix of woodland (bushland). We predicted (1) a net gain of soil nutrients at bushland sites (that is, inputs of nutrients > losses) and (2) a net loss of soil nutrients at glade sites (that is, inputs of nutrients < losses) following herbivore exclusion. As expected, soil N increased (by 28% after 17 years) with herbivore removal, but remained largely unchanged in the presence of herbivores at low-nutrient bushland sites. However, contrary to our expectations, soil total N in nutrient-rich glades also increased (+ 18%) when herbivores were removed, but declined when grazed (- 11%). Although the underlying mechanisms are unclear, we suggest that increased N fixation by Acacia spp., combined with increased canopy cover and associated tree leaf litter, resulted in elevated soil N following browser removal in low-nutrient bushland sites, while grazer-induced increases in the rate of N transformations between organic and mineral forms resulted in a more "open" N cycle (as evidenced by higher N mineralization rates and foliar N), with increased potential for N loss in gaseous forms, in grazed nutrient-rich glade sites. Grazers and browsers thus appear to affect the N cycle and create and reinforce heterogeneity in unique ways.