Phosphorus (P) is often an important limiting factor for crop yields, but rock phosphate as fertilizer is a non-renewable resource and expected to become scarce in the future. High P input levels in agriculture have led to environmental problems. One of the ways to tackle these issues simultaneously is improving phosphorus use efficiency (PUE) of the crops through breeding. In this review, we describe plant architectural and physiological traits important for PUE. Subsequently, we discuss efficient methods of screening for PUE traits. We address targeted cultivation methods, including solid and hydroponic systems, as well as testing methods, such as image analysis systems, and biomass and photosynthesis measurements. Genetic variation for PUE traits has been assessed in many crops, and genetics of PUE has been studied by quantitative trait loci (QTL) analyses and genome-wide association study. A number of genes involved in the plant’s response to low P have been characterized. These genes include transcription factors, and genes involved in signal transduction, hormonal pathways, sugar signalling, P saving metabolic pathways, and in P scavenging, including transporters and metabolites and/or ATP-ases mobilizing P in the soil. In addition, the role of microorganisms promoting PUE of plants, particularly arbuscular mycorrhizal fungi is discussed. An overview is given of methods for selecting for optimal combinations of plant and fungal genotypes, and their genetics, incl. QTLs and genes involved. In conclusion, significant progress has been made in selecting for traits for PUE, developing systems for the difficult but highly relevant root phenotyping, and in identifying QTLs and genes involved.