Species delimitation in the Cladonia gracilis group has long been known to be difficult due to morphological variability of taxa. The present study addresses the circumscription of species within this group, examining a number of specimens of the currently accepted taxa Cladonia coniocraea, C. cornuta subsp. cornuta, C. cornuta subsp. groenlandica, C. ecmocyna subsp. ecmocyna, C. ecmocyna subsp. intermedia, C. gracilis subsp. gracilis, C. gracilis subsp. elongata, C. gracilis subsp. tenerrima, C. gracilis subsp. turbinata, C. gracilis subsp. vulnerata, C. macroceras, C. maxima, and C. ochrochlora using genealogical concordance phylogenetic species recognition. We employed maximum parsimony, maximum likelihood and Bayesian methods of phylogenetic reconstructions based on DNA sequences of ITS rDNA, IGS rDNA, RPB2 and partially EF1-α regions. Our results indicate that the C. gracilis group is monophyletic but that most currently accepted taxa do not form monophyletic groups, with the exception of C. ecmocyna and C. cornuta subsp. cornuta. Different tests suggest that incomplete lineage sorting and sporadic recombination events are responsible for a phylogeny that largely lacks support. Our data also strongly suggest that C. coniocraea, C. cornuta subsp. groenlandica, and C. ochrochlora are conspecific, with C. coniocraea being the oldest available name. The morphological characters in the group are shown to be highly homoplasious, causing, in tandem with phenotypical plasticity of the taxa, the difficulties in delimiting species in the C. gracilis group.