Background We have used the genomic data in the Integrated Microbial Genomes system of the Department of Energy’s Joint Genome Institute to make predictions about rhizobial open reading frames that play a role in nodulation of host plants. The genomic data was screened by searching for ORFs conserved in α-proteobacterial rhizobia, but not conserved in closely-related non-nitrogen-fixing α-proteobacteria. Results Using this approach, we identified many genes known to be involved in nodulation or nitrogen fixation, as well as several new candidate genes. We knocked out selected new genes and assayed for the presence of nodulation phenotypes and/or nodule-specific expression. One of these genes, SMc00911, is strongly expressed by bacterial cells within host plant nodules, but is expressed minimally by free-living bacterial cells. A strain carrying an insertion mutation in SMc00911 is not defective in the symbiosis with host plants, but in contrast to expectations, this mutant strain is able to out-compete the S. meliloti 1021 wild type strain for nodule occupancy in co-inoculation experiments. The SMc00911 ORF is predicted to encode a “SodM-like” (superoxide dismutase-like) protein containing a rhodanese sulfurtransferase domain at the N-terminus and a chromate-resistance superfamily domain at the C-terminus. Several other ORFs (SMb20360, SMc01562, SMc01266, SMc03964, and the SMc01424-22 operon) identified in the screen are expressed at a moderate level by bacteria within nodules, but not by free-living bacteria. Conclusions Based on the analysis of ORFs identified in this study, we conclude that this comparative genomics approach can identify rhizobial genes involved in the nitrogen-fixing symbiosis with host plants, although none of the newly identified genes were found to be essential for this process.