Aluminum (Al) toxicity in acid soils significantly affects plant growth, agricultural productivity and ecosystem health. Here we investigated plant Al tolerance from evolutionary physiological, molecular, and ecological perspectives. Genetic similarity and phylogenetic analysis of Al tolerance-associated gene families showed that many of these were conserved from streptophyte algae to angiosperms, indicating land plants have evolved gradually in adaptation to Al-rich acid soil during plant terrestrialization. In particular, vacuolar phosphate transporter SPX-major facility superfamily (SPX-MFS) and inorganic phosphate (Pi) transporter 1 subfamily (PHT1s) of streptophyte algae showed higher genetic similarity to land plants than chlorophyte algae. PHT1 subfamily exhibited a significant expand during the evolution from streptophyte algae to liverworts and then to eudicots. Moreover, we identified an Al-tolerant Tibetan wild barley accession XZ29, showing high levels of Phosphorus(P)-containing glycolytic intermediates under Al stress. We found a new Al-tolerance mechanism that Al-induced Pi efflux from root elongation zone to chelate rhizosphere Al3+ and immobilization of Al with P reduce Al accumulation in barley root cells. These results indicated that Tibetan wild barley has evolved unique P transport and metabolism for the adaptation to harsh conditions in eastern and southeastern Tibet where acid soils contain high P.