BACKGROUND: Understanding the evolution of cultivated barley is important for two reasons. First, the evolutionary relationships between different landraces might provide information on the spread and subsequent development of barley cultivation, including the adaptation of the crop to new environments and its response to human selection. Second, evolutionary information would enable landraces with similar traits but different genetic backgrounds to be identified, providing alternative strategies for the introduction of these traits into modern germplasm. RESULTS: The evolutionary relationships between 651 barley landraces were inferred from the genotypes for 24 microsatellites. The landraces could be divided into nine populations, each with a different geographical distribution. Comparisons with ear row number, caryopsis structure, seasonal growth habit and flowering time revealed a degree of association between population structure and phenotype, and analysis of climate variables indicated that the landraces are adapted, at least to some extent, to their environment. Human selection and/or environmental adaptation may therefore have played a role in the origin and/or maintenance of one or more of the barley landrace populations. There was also evidence that at least some of the population structure derived from geographical partitioning set up during the initial spread of barley cultivation into Europe, or reflected the later introduction of novel varieties. In particular, three closely-related populations were made up almost entirely of plants with the daylength nonresponsive version of the photoperiod response gene PPD-H1, conferring adaptation to the long annual growth season of northern Europe. These three populations probably originated in the eastern Fertile Crescent and entered Europe after the initial spread of agriculture. CONCLUSIONS: The discovery of population structure, combined with knowledge of associated phenotypes and environmental adaptations, enables a rational approach to identification of landraces that might be used as sources of germplasm for breeding programs. The population structure also enables hypotheses concerning the prehistoric spread and development of agriculture to be addressed.