Frequent nutrient removals accompanying wood and crop harvests from rotational woodlot systems may contribute to declining site productivity and sustainability because of soil nutrient depletion. However, selecting for nutrient-efficient tree species may well sustain productivity under this system. To test this hypothesis, a randomized complete block experiment was adopted to assess effects of five tree species on soil nutrients status, nutrient use efficiency and wood yield in semi-arid Tanzania. After 5years rotation, top soils under Gliricidia sepium (Jaqua), Acacia polyacantha Willd. and Acacia mangium Willd. were the most fertile with soil organic carbon and exchangeable cation status raised close to those in natural Miombo systems. Soil inorganic N and extractable P levels reached sufficiency levels for subsequent maize culture. Wood productivity in tree fallows averaged three times higher than that of Miombo woodlands indicating the high potential of the woodlot system to supply fuelwood, and consequently relieve harvesting pressures on the natural forests. Acacia crassicarpa A. Cunn. ex Benth. produced the most wood (51Mgha−1) at low nutrient “costs” presumably due to high nutrient use efficiency. Wood yield of this species was 42 and 120% greater than that of A. polyacantha and A. nilotica, respectively, but contained comparatively less nutrients (42–60% less for P, K, and Ca). Gliricidia sepium and A. polyacantha returned the largest amount of nutrients through slash at harvests. Of all test species, A. crassicarpa exhibited the most promise to sustain wood production under rotational woodlot systems due to relatively high productivity and low nutrient export at harvest.