We identified novel physiological and genetic responses to phosphorus starvation in sorghum diversity lines that augment current knowledge of breeding for climate-smart crops in Europe. Phosphorus (P) deficiency and finite P reserves for fertilizer production pose a threat to future global crop production. Understanding root system architecture (RSA) plasticity is central to breeding for P-efficient crops. Sorghum is regarded as a P-efficient and climate-smart crop with strong adaptability to different climatic regions of the world. Here we investigated early genetic responses of sorghum RSA to P deficiency in order to identified genotypes with interesting root phenotypes and responses under low P. A diverse set of sorghum lines (n = 285) was genotyped using DarTSeq generating 12,472 quality genome wide single-nucleotide polymorphisms. Root phenotyping was conducted in a paper-based hydroponic rhizotron system under controlled greenhouse conditions with low and optimal P nutrition, using 16 RSA traits to describe genetic and phenotypic variability at two time points. Genotypic and phenotypic P-response variations were observed for multiple root traits at 21 and 42 days after germination with high broad sense heritability (0.38-0.76). The classification of traits revealed four distinct sorghum RSA types, with genotypes clustering separately under both low and optimal P conditions, suggesting genetic control of root responses to P availability. Association studies identified quantitative trait loci in chromosomes Sb02, Sb03, Sb04, Sb06 and Sb09 linked with genes potentially involved in P transport and stress responses. The genetic dissection of key factors underlying RSA responses to P deficiency could enable early identification of P-efficient sorghum genotypes. Genotypes with interesting RSA traits for low P environments will be incorporated into current sorghum breeding programs for later growth stages and field-based evaluations.