In many legumes, including Lotus japonicus and Medicago truncatula, susceptible root hairs are the primary sites for the initial signal perception and physical contact between the host plant and the compatible nitrogen-fixing bacteria that leads to the initiation of root invasion and nodule organogenesis. However, diverse mechanisms of nodulation have been described in a variety of legume species that do not rely on root hairs. To clarify the significance of root hairs during the L. japonicus-Mesorhizobium loti symbiosis, we have isolated and performed a detailed analysis of four independent L. japonicus root hair developmental mutants. We show that although important for the efficient colonization of roots, the presence of wild-type root hairs is not required for the initiation of nodule primordia (NP) organogenesis and the colonization of the nodule structures. In the genetic background of the L. japonicus root hairless 1 mutant, the nodulation factor-dependent formation of NP provides the structural basis for alternative modes of invasion by M. loti. Surprisingly, one mode of root colonization involves nodulation factor-dependent induction of NP-associated cortical root hairs and epidermal root hairs, which, in turn, support bacterial invasion. In addition, entry of M. loti through cracks at the cortical surface of the NP is described. These novel mechanisms of nodule colonization by M. loti explain the fully functional, albeit significantly delayed, nodulation phenotype of the L. japonicus ROOT HAIRLESS mutant.