The evolution of the RecA protein was analyzed using molecular phylogenetic techniques. Phylogenetic trees of all currently available complete RecA proteins were inferred using multiple maximum parsimony and distance matrix methods. Comparison and analysis of the trees reveal that the inferred relationships among these proteins are highly robust. The RecA trees show consistent subdivisions corresponding to many of the major bacterial groups found in trees of other molecules including the alpha, beta, gamma, delta, epsilon proteobacteria, cyanobacteria, high-GC gram-positives, and the Deinococcus-Thermus group. However, there are interesting differences between the RecA trees and these other trees. For example, in all the RecA trees the proteins from gram-positive species are not monophyletic. In addition, the RecAs of the cyanobacteria consistently group with those of the high-GC gram-positives. To evaluate possible causes and implications of these and other differences phylogenetic trees were generated for small-subunit rRNA sequences from the same (or closely related) species as represented in the RecA analysis. The trees of the two molecules using these equivalent species-sets are highly congruent and have similar resolving power for close, medium, and deep branches in the history of bacteria. The implications of the particular similarities and differences between the trees are discussed. Some of the features that make RecA useful for molecular systematics and for studies of protein evolution are also discussed.