Drylands count among the most globally extensive biomes, and while many desert and dry rangeland ecosystems are under threat, genetic structures of dryland species are still rarely studied. Artemisia frigida is one of the most widely distributed plant species in the temperate rangelands of Eurasia and North America, and it also dominates in many habitats of Mongolia due to its tolerance to low temperatures, drought and disturbance. Local environmental conditions and grazing pressure can influence species performance and affect spatial patterns of genetic diversity in contrasting ways, and our study set out to evaluate such effects on the genetic diversity and structure of A. frigida. We first developed new species-specific Simple Sequence Repeats (SSRs) markers using whole genome sequencing. We then analysed 11 populations of A. frigida that had been sampled along a large climatic gradient in Mongolia, which were sub-structured according to three levels of grazing intensity. Estimates of genetic diversity at the population level were high (H_O = 0.56, H_E = 0.73) and tended to increase with higher precipitation and soil nutrient availability. Grazing had no effect on genetic diversity, however, a high number of grazing-specific indicator alleles was found at grazed sites. Genetic differentiation among populations was extremely low (global G_ST = 0.034). Analysis of Molecular Variance revealed 5% variance between populations along the climatic gradient, with 3% of the variance being partitioned among different grazing intensity levels. We found no relationship between geographic and genetic distances, and thus no isolation by distance in this widely distributed species. The relatively low genetic structuring suggests that considerable gene flow exists among A. frigida populations across the rangelands of Mongolia, in spite of the pervasive grazing in the region.