Eucalyptus is the tree most widely planted in tropical countries to satisfy growing demand for wood products, but high yields require high fertilizer inputs. Introducing N2-fixing trees (NFT), such as Acacia mangium, has been proposed to improve soil fertility and aboveground tree biomass in Eucalyptus plantations. In addition to N inputs, NFT species may increase plant P nutrition through increased rates of organic P (Po) cycling. However, the positive effect of acacia on soil P availability and plant P nutrition was found to vary substantially between sites. The ability of acacia to improve P bioavailability might mainly depend on Po sequestration in microbial biomass, preventing Po mineralization by phosphatases and efficient Po recycling. This hypothesis was tested at two tropical sites, Itatinga (Brazil) and Kissoko (Congo) by measuring inorganic phosphate (Pi), Po and enzyme-labile Po in bicarbonate extracts from the topsoil collected from plots with Eucalyptus, acacias, or native vegetation. We used bicarbonate enzyme-labile Po after soil autoclaving as an indicator of microbial Po, and a Eucalyptus bioassay to measure the actual P bioavailability for Eucalyptus seedlings. At Itatinga, bicarbonate-Pi was very low, while Po was the main P form. Enzyme-labile Po was very weak in intact soils and high in autoclaved soils, indicating high immobilization in microbial biomass. At Kissoko, Po was highly enzyme-labile in both intact and autoclaved soils, especially from acacia plots, suggesting very low Po immobilization in microbial biomass. Growth and P accumulations in Eucalyptus seedlings were low in all soils at Itatinga and were the highest in Eucalyptus plants grown in acacia soils at Kissoko. Our results highlight the potential of acacia trees for improving P bioavailability for other tree species if labile Po enrichment in the soil provided by this N2-fixing tree is not locked into the microbial biomass.