The molecular evolution of the R2R3-MYB gene family is of great interest because it is one of the most important transcription factor gene families in the plant kingdom. Comparative analyses of a gene family may reveal important adaptive changes at the protein level and thereby provide insights that relate structure to function. We have performed a range of comparative and bioinformatics analyses on R2R3-MYB genes identified from the rice (Oryza sativa subsp. japonica and indica) and Arabidopsis genome sequences. The study provides an initial framework to investigate how different evolutionary lineages in a gene family evolve new functions. Our results reveal a remarkable excess of non-synonymous substitutions, an indication of adaptive selection on protein structure that occurred during the evolution of both helix1 and helix2 of rice R2R3-MYB DNA-binding domains. These flexible alpha-helix regions associated with high frequencies of excess non-synonymous substitutions may play critical roles in the characteristic packing of R2R3-MYB DNA-binding domains and thereby modify the protein-DNA interaction process resulting in the recognition of novel DNA-binding sites. Furthermore, a co-evolutionary pattern is found between the second alpha-helix of the R2 domain and the second alpha-helix of the R3 domain by examining all the possible alpha-helix pairings in both the R2 and R3 domains. This points to the functional importance of pairing interactions between related secondary structures.