This paper presents a vegetation map of the Gobi Gurvan Sayhan National Park, a large protected area in the semi-arid parts of southern Mongolia. The map was compiled in order to provide spatially explicit baseline data that were required for conservation management. The study area was covered by five partly overlapping Landsat ETM+ scenes. Vegetation was sampled at more than 600 sites using a modified Braun-Blanquet approach; locations were selected with the help of unsupervised classifications of the satellite scenes. Vegetation samples were initially classified with a phytosociological approach yielding four main groups of plant communities: mountain steppes, moist desert steppes of the upper pediments, dry desert steppes and extra-zonal vegetation. These groups comprised a total of 18 plant communities, which were subsequently used for the supervised classification of satellite images. Difficulties were expected due to the sparse vegetation cover typical for semi-deserts and steppe ecosystems, resulting in minor spectral differences among the different communities. However, independent validation of the map yielded an overall accuracy above 93%. Thus, the chosen set of methods proved suitable for the study region, and is currently employed for similar surveys in other southern Mongolian nature reserves.