Trapelioid fungi constitute a widespread group of mostly crust-forming lichen mycobionts that are key to understanding the early evolutionary splits in the Ostropomycetidae, the second-most species-rich subclass of lichenized Ascomycota. The uncertain phylogenetic resolution of the approximately 170 species referred to this group contributes to a poorly resolved backbone for the entire subclass. Based on a data set including 657 newly generated sequences from four ribosomal and four protein-coding gene loci, we tested a series of a priori and new evolutionary hypotheses regarding the relationships of trapelioid clades within Ostropomycetidae. We found strong support for a monophyletic group of nine core trapelioid genera but no statistical support to reject the long-standing hypothesis that trapelioid genera are sister to Baeomycetaceae or Hymeneliaceae. However, we can reject a sister group relationship to Ostropales with high confidence. Our data also shed light on several long-standing questions, recovering Anamylopsoraceae nested within Baeomycetaceae, elucidating two major monophyletic groups within trapelioids (recognized here as Trapeliaceae and Xylographaceae), and rejecting the monophyly of the genus Rimularia. We transfer eleven species of the latter genus to Lambiella and describe the genus Parainoa to accommodate a previously misunderstood species of Trapeliopsis. Past phylogenetic studies in Ostropomycetidae have invoked "divergence order" for drawing taxonomic conclusions on higher level taxa. Our data show that if backbone support is lacking, contrasting solutions may be recovered with different or added data. We accordingly urge caution in concluding evolutionary relationships from unresolved phylogenies.