The interactions of legumes with symbiotic nitrogen-fixing bacteria cause the formation of specialized lateral root organs called root nodules. It has been postulated that this root nodule symbiosis system has recruited factors that act in early signaling pathways (common SYM genes) partly from the ancestral mycorrhizal symbiosis. However, the origins of factors needed for root nodule organogenesis are largely unknown. NODULE INCEPTION (NIN) is a nodulation-specific gene that encodes a putative transcription factor and acts downstream of the common SYM genes. Here, we identified two Nuclear Factor-Y (NF-Y) subunit genes, LjNF-YA1 and LjNF-YB1, as transcriptional targets of NIN in Lotus japonicus. These genes are expressed in root nodule primordia and their translational products interact in plant cells, indicating that they form an NF-Y complex in root nodule primordia. The knockdown of LjNF-YA1 inhibited root nodule organogenesis, as did the loss of function of NIN. Furthermore, we found that NIN overexpression induced root nodule primordium-like structures that originated from cortical cells in the absence of bacterial symbionts. Thus, NIN is a crucial factor responsible for initiating nodulation-specific symbiotic processes. In addition, ectopic expression of either NIN or the NF-Y subunit genes caused abnormal cell division during lateral root development. This indicated that the Lotus NF-Y subunits can function to stimulate cell division. Thus, transcriptional regulation by NIN, including the activation of the NF-Y subunit genes, induces cortical cell division, which is an initial step in root nodule organogenesis. Unlike the legume-specific NIN protein, NF-Y is a major CCAAT box binding protein complex that is widespread among eukaryotes. We propose that the evolution of root nodules in legume plants was associated with changes in the function of NIN. NIN has acquired functions that allow it to divert pathways involved in the regulation of cell division to root nodule organogenesis.