Premise Phylogenetic trees of bryophytes provide important evolutionary context for land plants. However, published inferences of overall embryophyte relationships vary considerably. We performed phylogenomic analyses of bryophytes and relatives using both mitochondrial and plastid gene sets, and investigated bryophyte plastome evolution. Methods We employed diverse likelihood-based analyses to infer large-scale bryophyte phylogeny for mitochondrial and plastid data sets. We tested for changes in purifying selection in plastid genes of a mycoheterotrophic liverwort (Aneura mirabilis) and a putatively mycoheterotrophic moss (Buxbaumia), and compared 15 bryophyte plastomes for major structural rearrangements. Results Overall land-plant relationships conflict across analyses, generally weakly. However, an underlying (unrooted) four-taxon tree is consistent across most analyses and published studies. Despite gene coverage patchiness, relationships within mosses, liverworts, and hornworts are largely congruent with previous studies, with plastid results generally better supported. Exclusion of RNA edit sites restores cases of unexpected non-monophyly to monophyly for Takakia and two hornwort genera. Relaxed purifying selection affects multiple plastid genes in mycoheterotrophic Aneura but not Buxbaumia. Plastid genome structure is nearly invariant across bryophytes, but the tufA locus, presumed lost in embryophytes, is unexpectedly retained in several mosses. Conclusions A common unrooted tree underlies embryophyte phylogeny, [(liverworts, mosses), (hornworts, vascular plants)]; rooting inconsistency across studies likely reflects substantial distance to algal outgroups. Analyses combining genomic and transcriptomic data may be misled locally for heavily RNA-edited taxa. The Buxbaumia plastome lacks hallmarks of relaxed selection found in mycoheterotrophic Aneura. Autotrophic bryophyte plastomes, including Buxbaumia, hardly vary in overall structure.