Nitrogen (N) fixing trees including many species of Acacia are an important though variable component of savanna ecosystems. It is known that these trees enrich the soil with carbon (C) and N, but their effect on the combined C:N:P stoichiometry in soil is less well understood. Theory suggests that they might reduce available phosphorus (P), creating a shift from more N-limited conditions in grass-dominated to more P-limited conditions in tree-dominated sites, which in turn could feed back negatively on the trees’ capacity to fix N. We studied the effects of Acacia zanzibarica tree density upon soil and foliar N:P stoichiometry, and the N2-fixation rates of trees and leguminous herbs in a humid Tanzanian savanna. Foliar N:P ratios and N2-fixation rates of trees remained constant across the density gradient, whereas soil C, N and organic P pools increased. In contrast, the N:P ratio of grasses increased and N2-fixation rates of leguminous herbs decreased with increasing tree density, indicating a shift towards more P-limited conditions for the understory vegetation. These contrasting responses suggest that trees and grasses have access to different sources of N and P, with trees being able to access P from deeper soil layers and perhaps also utilizing organic forms more efficiently.