Foxtail millet [Setaria italica (L.) P. Beauv.] is the second most important millet species globally and is adapted to cultivation in diverse environments. Like its wild progenitor, green foxtail [S. viridis (L.) P. Beauv.], it is a model species for C4 photosynthetic pathways and stress tolerance genes in related bioenergy crops. We addressed questions regarding the evolution and spread of foxtail millet through a population genomic study of landraces from across its cultivated range in Europe, Asia, and Africa. We sought to determine population genomic structure and the relationship of domesticated lineages relative to green foxtail. Further, we aimed to identify genes involved in environmental stress tolerance that have undergone differential selection between geographical and genetic groups. Foxtail millet landrace accessions (n = 328) and green foxtail accessions (n = 12) were sequenced by genotyping-by-sequencing (GBS). After filtering, 5,677 single nucleotide polymorphisms (SNPs) were retained for the combined foxtail millet−green foxtail dataset and 5,020 for the foxtail millet dataset. We extended geographic coverage of green foxtail by including previously published GBS sequence tags, yielding a 4,515-SNP dataset for phylogenetic reconstruction. All foxtail millet samples were monophyletic relative to green foxtail, suggesting a single origin of foxtail millet, although no group of foxtail millet was clearly the most ancestral. Four genetic clusters were found within foxtail millet, each with a distinctive geographical distribution. These results, together with archaeobotanical evidence, suggest plausible routes of spread of foxtail millet. Selection scans identified nine candidate genes potentially involved in environmental adaptations, particularly to novel climates encountered, as domesticated foxtail millet spread to new altitudes and latitudes.