During the past century, the biomass of woody species has increased in many grassland and savanna ecosystems. As many of these species fix nitrogen symbiotically, they may alter not only soil nitrogen (N) conditions but also those of phosphorus (P). We studied the N-fixing shrub Dichrostachys cinerea in a mesic savanna in Zambia, quantifying its effects upon pools of soil N, P, and carbon (C), and availabilities of N and P. We also evaluated whether these effects induced feedbacks upon the growth of understory vegetation and encroaching shrubs. Dichrostachys cinerea shrubs increased total N and P pools, as well as resin-adsorbed N and soil extractable P in the top 10-cm soil. Shrubs and understory grasses differed in their foliar N and P concentrations along gradients of increasing encroachment, suggesting that they obtained these nutrients in different ways. Thus, grasses probably obtained them mainly from the surface upper soil layers, whereas the shrubs may acquire N through symbiotic fixation and probably obtain some of their P from deeper soil layers. The storage of soil C increased significantly under D. cinerea and was apparently not limited by shortages of either N or P. We conclude that the shrub D. cinerea does not create a negative feedback loop by inducing P-limiting conditions, probably because it can obtain P from deeper soil layers. Furthermore, C sequestration is not limited by a shortage of N, so that mesic savanna encroached by this species could represent a C sink for several decades.