Unraveling the phylogenetic relationships between the four major lineages of terrestrial plants (mosses, liverworts, hornworts, and vascular plants) is essential for an understanding of the evolution of traits specific to land plants, such as their complex life cycles, and the evolutionary development of stomata and vascular tissue. Well supported phylogenetic hypotheses resulting from different data and methods are often incongruent due to processes of nucleotide evolution that are difficult to model, for example substitutional saturation and composition heterogeneity. We reanalysed a large published dataset of nuclear data and modelled these processes using degenerate-codon recoding and tree-heterogeneous composition substitution models. Our analyses resolved bryophytes as a monophyletic group and showed that the nonnonmonophyly of the clade that is supported by the analysis of nuclear nucleotide data is due solely to fast-evolving synonymous substitutions. The current congruence among phylogenies of both nuclear and chloroplast analyses lent considerable support to the conclusion that the bryophytes are a monophyletic group. An initial split between bryophytes and vascular plants implies that the bryophyte life cycle (with a dominant gametophyte nurturing an unbranched sporophyte) may not be ancestral to all land plants and that stomata are likely to be a symplesiomorphy among embryophytes.