Low phosphate (Pi) availability and high aluminum (Al) toxicity constitute two major plant mineral nutritional stressors that limit plant productivity on acidic soils. Advances toward the identification of genes and signaling networks that are involved in both stresses in model plants such as Arabidopsis thaliana and rice (Oryza sativa), and in other plants as well have revealed that some factors such as organic acids (OAs), cell wall properties, phytohormones, and iron (Fe) homeostasis are interconnected with each other. Moreover, OAs are involved in recruiting of many plantgrowth-promoting bacteria that are able to secrete both OAs and phosphatases to increase Pi availability and decrease Al toxicity. In this review paper, we summarize these mutual mechanisms by which plants deal with both Al toxicity and P starvation, with emphasis on OA secretion regulation, plant-growth-promoting bacteria, transcription factors, transporters, hormones, and cell wall-related kinases in the context of root development and root system architecture remodeling that plays a determinant role in improving P use efficiency and Al resistance on acidic soils.