Climatically extreme regions such as the polar deserts of the McMurdo Dry Valleys (78° S) in Continental Antarctica are key areas for a better understanding of changes in ecosystems. Therefore, it is particularly important to analyze and communicate current patterns of biodiversity in these sensitive areas, where precipitation mostly occurs in form of snow and liquid water is rare. Humidity provided by dew, clouds, and fog are the main water sources, especially for rock-dwelling crustose lichens as one of the most common vegetation-forming organisms. We investigated the diversity and interaction specificity of myco-/photobiont associations of 232 crustose lichen specimens, collected along an elevational gradient (171–959 m a.s.l.) within the McMurdo Dry Valleys. The mycobiont species and photobiont OTUs were identified by using three markers each (nrITS, mtSSU, RPB1, and nrITS, psbJ-L, COX2). Elevation, positively associated with water availability, turned out to be the key factor explaining most of the distribution patterns of the mycobionts. Pairwise comparisons showed Lecidea cancriformis and Rhizoplaca macleanii to be significantly more common at higher elevations and Carbonea vorticosa and Lecidea polypycnidophora at lower elevations. Lichen photobionts were dominated by the globally distributed Trebouxia OTU, Tr_A02 which occurred at all habitats. Network specialization resulting from myco-/photobiont bipartite network structure varied with elevation and associated abiotic factors. Along an elevational gradient, the spatial distribution, diversity, and genetic variability of the lichen symbionts appear to be mainly influenced by improved water relations at higher altitudes.