Leguminous trees have a potential for phytoremediation of oil-contaminated areas for its symbiotic association with nitrogen-fixing bacteria and arbuscular mycorrhizal fungi (AMF). This study selects leguminous tree associated with symbiotic microorganisms that have the potential to remediate petroleum-contaminated soil. Seven species of trees were tested: Acacia angustissima, Acacia auriculiformis, Acacia holosericea, Acacia mangium, Mimosa artemisiana, Mimosa caesalpiniifolia, and Samanea saman. They were inoculated with AMF mix and nitrogen-fixing bacteria mix and cultivated over five oil levels in soils, with five replicates. The decreasing of total petroleum hydrocarbons (TPH) values occurred especially with S. saman and its symbiotic microorganisms on highest oil soil contamination. Despite the large growth of A. angustissima and M. caesalpiniifolia on the highest level of oil, these species and its inoculated microorganisms did not reduce the soil TPH. Both plants were hydrocarbon tolerant but not able to remediate the polluted soil. In contrast were significative hydrocarbon decrease with M. artemisiana under high oil concentrations, but plant growth was severely affected. Results suggest that the ability of the plants to decrease the soil concentration of TPH is not directly related to its growth and adaptation to conditions of contamination, but the success of the association between plants and its symbionts that seem to play a critical role on remediation efficiency.