This paper continues a revision of generic concepts in the parmelioid lichens using molecular data in order to reach a consensus among lichenologists over which segregates proposed over the last two decades should be accepted. Here we employ data from three gene portions to provide a basis for a revised generic concept of the brown parmelioid lichens hitherto classified in Melanelia. The phylogeny was studied using a Bayesian analysis of a combined data set of nuclear ITS, LSU rDNA and mitochondrial SSU rDNA sequences. 173 new sequences were obtained from 38 specimens of 15 Melanelia species, 37 related parmelioid species, and eight non-parmelioid species. The results indicate that Melanelia is not monophyletic but falls into four different clades. The genus Melanelia is restricted here to a small group of saxicolous lichens related to the type species M. stygia, and with bifusiform conidia, while the remaining species, most of which are primarily corticolous and have mainly cylindrical to filiform conidia, belong to two other clades recognised as two new genera: Melanelixia and Melanohalea, to accommodate the M. exasperata and M. glabra groups, respectively. 27 new combinations are made. The epicortex of Melanelixia species have pores or special structures termed here ‘fenestrations’, while most Melanohalea species are pseudocyphellate. Pleurosticta links to the Melanohalea clade but without strong support, and the phylogenetic position of M. disjuncta and its related species remains uncertain, linking with the Xanthoparmelia (syn. Neofuscelia) clade but also without strong support.