Phosphate (Pi) availability is a major factor limiting growth, development, and productivity of plants. In both ecological and agricultural contexts, plants often grow in soils with low soluble phosphate content. Plants respond to this situation by a series of developmental and metabolic adaptations that are aimed at increasing the acquisition of this vital nutrient from the soil, as well as to sustain plant growth and survival. The development of a comprehensive understanding of how plants sense phosphate deficiency and coordinate the responses via signaling pathways has become of major interest, and a number of signaling players and networks have begun to surface for the regulation of the phosphate-deficiency response. In practice, application of such knowledge to improve plant Pi nutrition is hindered by complex cross-talks, which are emerging in the face of new data, such as the coordination of the phosphate-deficiency signaling networks with those involved with hormones, photo-assimilates (sugar), as well as with the homeostasis of other ions, such as iron. In this review, we focus on these cross-talks and on recent progress in discovering new signaling players involved in the Pi-starvation responses, such as proteins having SPX domains.