Bacterial infection of interior tissues of legume root nodules is controlled at the epidermal cell layer and is closely coordinated with progressing organ development. Using spontaneous nodulating Lotus japonicus plant mutants to uncouple nodule organogenesis from infection, we have determined the role of 16 genes in these two developmental processes. We show that host-encoded mechanisms control three alternative entry processes operating in the epidermis, the root cortex and at the single cell level. Single cell infection did not involve the formation of trans-cellular infection threads and was independent of host Nod-factor receptors and bacterial Nod-factor signals. In contrast, Nod-factor perception was required for epidermal root hair infection threads, whereas primary signal transduction genes preceding the secondary Ca2+ oscillations have an indirect role. We provide support for the origin of rhizobial infection through direct intercellular epidermal invasion and subsequent evolution of crack entry and root hair invasions observed in most extant legumes.