We investigated the epiphytic lichen community growing on salt-tolerant shrubs around the margins of playas in the Great Basin Desert. Data from 82 sites in and around playas throughout the region are analyzed. Of the 29 species of epiphytic lichens encountered, a faithful core community of 8 species regularly co-occurred at most playa sites. Two of these species are new to science: Lecania clairii sp. nov. is similar to L. fuscella but consistently produces a purple pigment in the epihymenium, has strictly 8-spored asci, strongly capitate, pigmented paraphyses, and more strongly swollen cells in the amphithecial cortex. Rinodina salinaria sp. nov. is similar to and co-occurs with R. lobulata but consistently lacks the pigment Sedifolia-gray; additionally, its apothecia remain immersed longer, and it has smaller ascospores. The most abundant lichen encountered was Calogaya ferrugineoides, until recently known only from Central Asia. Another Central Asian species, Calogaya polycarpoides, is reported for the first time for North America. Two lichenicolous fungi are common in this community, Arthonia molendoi and another species new to science, Lichenochora endocalogaya sp. nov. The latter is similar to L. xanthoriae but occurs on a different host, Calogaya ferrugineoides instead of Rusavskia elegans, and does not induce the formation of galls. The range and ecology of this halophytic community is discussed and compared with other epiphytic communities found in the Great Basin Desert.