Phosphorus (P) is an essential plant nutrient, but its availability is often limited in soil. Here, we studied changes in the transcriptome and in nutrient element concentrations in leaves and roots of poplars (Populus × canescens) in response to P deficiency. P starvation resulted in decreased concentrations of S and major cations (K, Mg, Ca), in increased concentrations of N, Zn and Al, while C, Fe and Mn were only little affected. In roots and leaves >4,000 and >9,000 genes were differently expressed upon P starvation. These genes clustered in eleven co-expression modules of which seven were correlated with distinct elements in the plant tissues. One module (4.7% of all differentially expressed genes) was strongly correlated with changes in the P concentration in the plant. In this module the GO term "response to P starvation" was enriched with phosphoenolpyruvate carboxylase kinases, phosphatases and pyrophosphatases as well as regulatory domains such as SPX, but no phosphate transporters. The P-related module was also enriched in genes of the functional category "galactolipid synthesis". Galactolipids substitute phospholipids in membranes under P limitation. Two modules, one correlated with C and N and the other with biomass, S and Mg, were connected with the P-related module by co-expression. In these modules GO terms indicating "DNA modification" and "cell division" as well as "defense" and "RNA modification" and "signaling" were enriched; they contained phosphate transporters. Bark storage proteins were among the most strongly upregulated genes in the growth-related module suggesting that N, which could not be used for growth, accumulated in typical storage compounds. In conclusion, weighted gene coexpression network analysis revealed a hierarchical structure of gene clusters, which separated phosphate starvation responses correlated with P tissue concentrations from other gene modules, which most likely represented transcriptional adjustments related to down-stream nutritional changes and stress.