RecA family proteins pair two DNAs with the same sequence to promote strand exchange during homologous recombination. To understand how RecA proteins search for and recognize homology, we sought to determine the length of homologous sequence that permits RecA to start its reaction. Specifically, we analyzed the effect of sequence heterogeneity on the association rate of homologous DNA with RecA/single-stranded DNA complex. We assumed that the reaction can start with equal likelihood at any point in the DNA, and that sequence heterogeneity abolishes some possible initiation sites. This analysis revealed that the effective recognition size is five or six nucleotides, larger than the three nucleotides recognized by a RecA monomer. Because the first DNA is elongated 1.5-fold by intercalation of amino acid residues of RecA every three bases, the second bound DNA must be elongated to pair with the first. Because this length is similar to estimates based on the strand-exchange reaction or DNA pair formation, the homology test is likely to occur primarily at the association step. The energetic difference due to the absence of hydrogen bonding is too small to discriminate single-nucleotide heterogeneity over a five- or six-nucleotide sequence. The selection is very likely to be made kinetically, and probably involves some structural factor other than Watson–Crick hydrogen bonding. It would be valuable to determine whether this is also the case for other biological reactions involving DNA base complementarity, such as replication, transcription, and translation.