Flowering plant mitochondrial DNAs are characterized by molecular peculiarities, which are absent in bryophytes or algae. Our project addressed mitochondrial genomes in early, nonflowering vascular plants (i.e. gymnosperms, ferns and lycophytes), for which no complete mtDNA sequences were hitherto available. We determined the complete mitochondrial genomes of the lycophytes Isoetes engelmannii (quillwort) and Selaginella moellendorffii (spikemoss) and found that particular features characterizing plant mtDNAs – such as highly frequent mitochondrial genome recombination, insertion of foreign chloroplast or nuclear DNA and trans-splicing introns are present in abundance. Additionally, yet more molecular novelties were discovered in the lycophyte mtDNAs, which include a first trans-splicing group I intron, record amounts of RNA editing exceeding 2,000 positions of pyrimidine conversions and particular small group II introns in Isoetes or the complete absence of tRNA genes in Selaginella mtDNA. Given the plethora of interesting phenomena in the lycophytes representing the most ancient surviving vascular plant lineage – and the insight emerging at the same time that gymnosperm mtDNA is largely flowering-plant-like – we performed complete mitochondrial transcriptome analyses in the lycophytes, which confirmed functional transcript maturation via complex splicing and abundant RNA editing also in rRNAs and tRNAs. Additionally, larger parts (~70%) of the fern Gleichenia dicarpa mtDNA were determined, although this mitochondrial genome could as yet not be fully assembled given its extraordinary complexity. However, yet further idiosyncrasies are already apparent in Gleichenia mtDNA, among which numerous integrated mobile DNA elements, including a complete retrotransposon, are the most prominent. We conclude that the emergence of tracheophytes as a major evolutionary innovation of land plant life coincided with a molecular revolution in the mitochondrial genomes after split form the hornwort lineage.