Legume plants are able to interact symbiotically with soil bacteria to form nitrogen-fixing root nodules. Although specific recognition between rhizobia and legume species has been extensively characterized, plant molecular determinants that govern the preferential colonization by different strains within a single rhizobium species have received little attention. We found that the C subunit of the heterotrimeric nuclear factor NF-Y from common bean (Phaseolus vulgaris) NF-YC1 plays a key role in the improved nodulation seen by more efficient strains of rhizobia. Reduction of NF-YC1 transcript levels by RNA interference (RNAi) in Agrobacterium rhizogenes-induced hairy roots leads to the arrest of nodule development and defects in the infection process with either high or low efficiency strains. Induction of three G2/M transition cell cycle genes in response to rhizobia was impaired or attenuated in NF-YC1 RNAi roots, suggesting that this transcription factor might promote nodule development by activating cortical cell divisions. Furthermore, overexpression of this gene has a positive impact on nodulation efficiency and selection of Rhizobium etli strains that are naturally less efficient and bad competitors. Our findings suggest that this transcription factor might be part of a mechanism that links nodule organogenesis with an early molecular dialogue that selectively discriminates between high- and low-quality symbiotic partners, which holds important implications for optimizing legume performance.