Common bean cultivars are nodulated preferentially by Rhizobium etli lineages from the same center of host diversification. Nodulation was found to be earlier and numerous in bean plants inoculated with the cognate strain. We predicted that analysis of transcripts at early stages of the interaction between host and rhizobium would identify plant genes that are most likely to be involved in this preferential nodulation. Therefore, we applied a suppressive subtractive hybridization approach in which cDNA from a Mesoamerican cultivar inoculated with either the more- or less-efficient strain of R. etli was used as the driver and the tester, respectively. Forty-one independent tentative consensus sequences (TCs) were obtained and classified into different functional categories. Of 11 selected TCs, 9 were confirmed by quantitative reverse-transcriptase polymerase chain reaction. Two genes show high homology to previously characterized plant receptors. Two other upregulated genes encode for Rab11, a member of the small GTP-binding protein family, and HAP5, a subunit of the heterotrimeric CCAAT-transcription factor. Interestingly, one of the TCs encodes for an isoflavone reductase, which may lead to earlier Nod factor production by specific strains of rhizobia. The transcript abundance of selected cDNAs also was found to be higher in mature nodules of the more efficient interaction. Small or no differences were observed when an Andean bean cultivar was inoculated with a cognate strain, suggesting involvement of these genes in the strain-specific response. The potential role of these genes in the early preferential symbiotic interaction is discussed.