Many fungal species occur across a wide variety of habitats. Particularly lichens, fungi that form symbioses with photosynthetic algae or bacteria, have evolved a remarkable tolerance for environmental extremes. Despite their ecological importance and ubiquity, we know little about the genetic basis of adaptive differentiation in natural fungal populations. Here we studied patterns of genome-wide population differentiation in the lichen-forming fungus Lasallia pustulata along an elevation gradient in the Mediterranean region ranging from 100 to 1,300 m altitude. By sequencing pools of individuals from six populations along the cline, we found evidence for strong genetic differentiation between lowland and highland populations. This was despite short geographical distances (<10 km) the high levels of gene flow between populations. We identified several candidate genes that strongly correlate in frequency with environmental variables, and genes that are target of positive selection, particularly in the lower altitude populations (100 - 800 m a.s.l.). Functional annotations of these genes point to a number of important biological functions associated with stress response and local environmental adaptation. Our results provide a first genome-wide perspective on the adaptive differentiation of natural lichen populations.