The evolutionary emergence of land plant body plans transformed the planet. However, our understanding of this formative episode is mired in the uncertainty associated with the phylogenetic relationships among bryophytes (hornworts, liverworts, and mosses) and tracheophytes (vascular plants). Here we attempt to clarify this problem by analyzing a large transcriptomic dataset with models that allow for compositional heterogeneity between sites. Zygnematophyceae is resolved as sister to land plants, but we obtain several distinct relationships between bryophytes and tracheophytes. Concatenated sequence analyses that can explicitly accommodate site-specific compositional heterogeneity give more support for a mosses-liverworts clade, “Setaphyta,” as the sister to all other land plants, and weak support for hornworts as the sister to all other land plants. Bryophyte monophyly is supported by gene concatenation analyses using models explicitly accommodating lineage-specific compositional heterogeneity and analyses of gene trees. Both maximum-likelihood analyses that compare the fit of each gene tree to proposed species trees and Bayesian supertree estimation based on gene trees support bryophyte monophyly. Of the 15 distinct rooted relationships for embryophytes, we reject all but three hypotheses, which differ only in the position of hornworts. Our results imply that the ancestral embryophyte was more complex than has been envisaged based on topologies recognizing liverworts as the sister lineage to all other embryophytes. This requires many phenotypic character losses and transformations in the liverwort lineage, diminishes inconsistency between phylogeny and the fossil record, and prompts re-evaluation of the phylogenetic affinity of early land plant fossils, the majority of which are considered stem tracheophytes.