Nutrient availability and salinity of the soil affect growth and development of plant roots. Here, we describe how phosphate availability affects root system architecture (RSA) of Arabidopsis and how phosphate levels modulate responses of the root to salt stress. Phosphate (Pi) starvation reduced main root length and increased the number of lateral roots of Arabidopsis Col-0 seedlings. In combination with salt, low Pi dampened the inhibiting effect of mild salt stress (75mM) on all measured RSA components. At higher NaCl concentrations, the Pi deprivation response prevailed over the salt stress only for lateral root elongation. The Pi deprivation response of lateral roots appeared to be oppositely affected by abscisic acid (ABA) signaling compared to the salt stress response. Natural variation in the response to the combination treatment of salt and Pi starvation within 330 Arabidopsis accessions could be grouped into four response patterns. When exposed to double stress, in general lateral roots prioritized responses to salt, while the effect on main root traits was additive. Interestingly, these patterns were not identical for all accessions studied and multiple strategies to integrate the signals from Pi deprivation and salinity were identified. By Genome Wide Association Mapping (GWAS) 13 genomic loci were identified as putative factors integrating responses to salt stress and Pi starvation. From our experiments, we conclude that Pi starvation interferes with salt responses mainly at the level of lateral roots and that large natural variation exists in the available genetic repertoire of accessions to handle the combination of stresses.