The popular view that plant mitochondrial genome evolves slowly in sequence has been recently challenged by the extraordinarily high substitution rates of mtDNA documented mainly from several angiosperm genera, but high substitution rate acceleration accompanied with great length variation has been very rarely reported in plant mitochondrial genes. Here, we studied evolution of the mitochondrial rps3 gene that encodes the ribosomal small subunit protein 3 and found a dramatically high variation in both length and sequence of an exon region of it in Conifer II. A sequence comparison between cDNA and genomic DNA showed that there are no RNA editing sites in the Conifer II rps3 gene. Southern blotting analyses of the total DNA and mtDNA, together with the real-time PCR analysis, showed that rps3 exists as a single mitochondrial locus in gymnosperms. It is very likely that the Conifer II rps3 gene has experienced retroprocessing, i.e., the re-integration of its cDNA into the mitochondrial genome, followed by an evolutionary acceleration due to the intron loss. In addition, the phylogenetic analysis of rps3 supports the sister relationship between conifers and Gnetales. In particular, the monophyly of conifer II is strongly supported by the shared loss of two rps3 introns. Our results also indicate that the mitochondrial gene tree would be affected in topology when the 'edited' paralogs are analyzed together with their genomic sequences.