Catalytic RNAs are often regarded as molecular fossils from the RNA World, yet it is usually difficult to get more specific information about their evolution. Here we have investigated the coevolution of group II intron RNA structures with their intron-encoded reverse transcriptases (RTs). Unlike group I introns, there has been no obvious reshuffling between intron RNA structures and ORFs. Of the six classes of intron structures that encode ORFs, three are conventional forms of group II A1, B1, and B2 secondary structures, whereas the remaining classes are bacterial, are possibly associated with the most primitive ORFs, and have unusual features and hybrid features of group IIA and group IIB intron structures. Based on these data, we propose a new model for the evolution of group II introns, designated the retroelement ancestor hypothesis, which predicts that the major RNA structural forms of group II introns developed through coevolution with the intron-encoded protein rather than as independent catalytic RNAs, and that most ORF-less introns are derivatives of ORF-containing introns. The model is supported by the distribution of ORF-containing and ORF-less introns, and by numerous examples of ORF-less introns that contain ORF remnants.