Herbivores impact nutrient availability and cycling, and the net effect of herbivory on soil nutrients is generally assumed to be positive in nutrient-rich environments and negative in nutrient-poor ones. This is, however, far from a uniform pattern, and there is a recognized need to investigate any interactive effects of herbivory and habitat fertility (i.e., plant C/N ratios) on soil nutrient availabilities. We determined long-term effects of reindeer on soil extractable nitrogen (N) and phosphorus (P) and their net mineralization rates along a fertility gradient of plant carbon (C) to N and P ratios in arctic tundra. Our results showed that reindeer had a positive effect on soil N in the more nutrient-poor sites and a negative effect on soil P in the more nutrient-rich sites, which contrasts from the general consensus. The increase in N availability was linked to a decrease in plant and litter C/N ratios, suggesting that a shift in vegetation composition toward more graminoids favors higher N cycling. Soil P availability was not as closely linked to the vegetation and is likely regulated more by herbivore-induced changes in soil physical and chemical properties. The changes in soil extractable N and P resulted in higher soil N/P ratios, suggesting that reindeer could drive the vegetation toward P-limitation. This research highlights the importance of including both the elements N and P and conducting studies along environmental gradients in order to better understand the interactive effects of herbivory and habitat fertility on nutrient cycling and primary production.