1. Conservation of nomadic ungulates presents significant conservation challenges because of unpredictability in their movements and space use. Long-term studies on nomadic ungulates offering insights into the variability in space use within and between years are largely missing but are necessary to develop effective conservation strategies. 2. We examined the temporal variability in space-use of 22 Mongolian gazelle, tracked for one to three years with GPS and used the resulting movement patterns to evaluate conservation strategies associated with their nomadic movements in the intact open-plain grassland in Mongolia. 3. Individuals exhibited a high degree of variability in space use within and between years, often using different wintering areas in different years. The individual range size varied as much as threefold between years, with an estimated average annual individual range size of ~19,000 km2 and a lifetime range of ~100,000 km2. 4. Comparing simulated and empirical GPS trajectories for the Mongolian gazelle showed that they avoided disturbed areas (e.g., oil fields) and did not prefer protected areas. Importantly, no single protected area in the region was large enough to cover the annual range of any of the tracked gazelle. 5. Because of their wide-ranging movements, the presence of linear infrastructure and the resulting barrier effects are a particular concern. We found that fences along the national border were absolute barriers affecting movements of about 80% of all tracked individuals. When gazelle encounter the border fence, they moved a median distance of 11 km along fences, suggesting frequent crossing options are needed to make barriers permeable. 6. Synthesis and applications. We show that for nomadic ungulates whose space use varies greatly across years, multi-year movement data is essential for sound conservation planning. We emphasize that place based approaches alone are insufficient to conserve these wide-ranging species and that linear infrastructure is of particular concern. Because nomadic ungulates lack fidelity to certain movement corridors we advocate integrated land use planning that prioritizes permeability across the entire landscape and facilitates long-distance movements in arid and semi-arid regions.