Parmelioid lichens comprise about 1500 species and have a worldwide distribution. Numerous species are widely distributed and well known, including important bioindicators for atmospheric pollution. The phylogeny and classification of parmelioid lichens has been a matter of debate for several decades. Previous studies using molecular data have helped to establish hypotheses of the phylogeny of certain clades within this group. In this study, we infer the phylogeny of major clades of parmelioid lichens using DNA sequence data from two nuclear loci and one mitochondrial locus from 145 specimens (117 species) that represent the morphological and chemical diversity in these taxa. Parmelioid lichens are not monophyletic; however, a core group is strongly supported as monophyletic, excluding Arctoparmelia and Melanelia s. str., and including Parmeliopsis and Parmelaria. Within this group, seven well-supported clades are found, but the relationships among them remain unresolved. Stochastic mapping on a MC/MCMC tree sampling was employed to infer the evolution of two morphological and two chemical traits believed to be important for the evolutionary success of these lichens, and have also been used as major characters for classification. The results suggest that these characters have been gained and lost multiple times during the diversification of parmelioid lichens.