Heterodermia Trevis. is a morphologically and taxonomically diverse genus of lichenized fungi with numerous centers of diversity worldwide. It is traditionally distinguished from other Physciaceae by a prosoplectenchymatous upper cortex and thick-walled spores; however, recent studies, both morphological and phylogenetic, have delimited new genera within Heterodermia s.l., adding complexity to traditional circumscription of the genus. Here, we present a study of the evolution of several key morphological traits in Heterodermia s.l. by compiling one of the most densely sampled phylogenies of the genus to date and utilizing ancestral trait reconstruction and k-means clustering to reconstruct character evolution. We sampled and scored data for 25 species spanning six major groups for eight characters used by previous workers to delimit lineages within Heterodermia. These included: algal layer continuity, anthraquinone pigmentation, depsidone presence/absence, growth habit, lobe apex morphology, lower cortex presence/absence, rhizine branching, and spore type. Results from these analyses show that the evolutionary history of Heterodermia is characterized by parallel evolution, consequently rendering groups of morphologically similar species non-monophyletic. Given a lack of emergence of any clear morphological synapomorphies to define each of the major clades, our results support recognition of all species sampled here under the name Heterodermia s.l. rather than under other, recently segregated generic names. Finally, as a part of the authors’ comprehensive field inventory of lichens of the southern Rocky Mountains, two species of Heterodermia new to science were discovered and are described based on morphological, chemical, and phylogenetic characters: Heterodermia caesiosora sp. nov. and Heterodermia exuberans sp. nov. Heterodermia caesiosora is preliminarily assessed as Critically Endangered and H. exuberans as Endangered following IUCN guidelines. They are restricted to mesic canyons and north facing slopes of montane-subalpine transition zones (~8,000–9,500 ft. elevation), mostly in the Front Range of the southern Rocky Mountains. The new combination Heterodermia guzmaniana comb. nov. is also provided. Additional evidence would help more clearly resolve patterns of character evolution—including revisions to generic delimitation—in this diverse, cosmopolitan group of lichens. Keywords: Anaptychia, ancestral state reconstruction, fieldwork, internal transcribed spacer, Klauskalbia, k-means clustering, Leucodermia, lichenized fungi, molecular phylogeny, new species, Polyblastidium, Rocky Mountain, species description, taxonomy.