Rhizobial Nod factors induce plant responses and facilitate bacterial infection, leading to the development of nitrogen-fixing root nodules on host legumes. Nodule initiation is highly dependent on Nod-factor structure and, hence, on at least some of the nodulation genes that encode Nod-factor production. Here, we report the effects of mutations in Mesorhizobium loti R7A nodulation genes on nodulation of four Lotus spp. and on Nod-factor structure. Most mutants, including a ΔnodSΔnolO double mutant that produced Nod factors lacking the carbamoyl and possibly N-methyl groups on the nonreducing terminal residue, were unaffected for nodulation. R7AΔnodZ and R7AΔnolL mutants that produced Nod factors without the (acetyl)fucose on the reducing terminal residue had a host-specific phenotype, forming mainly uninfected nodule primordia on Lotus filicaulis and L. corniculatus and effective nodules with a delay on L. japonicus. The mutants also showed significantly reduced infection thread formation and Nin gene induction. In planta complementation experiments further suggested that the acetylfucose was important for balanced signaling in response to Nod factor by the L. japonicus NFR1/NFR5 receptors. Overall the results reveal differences in the sensitivity of plant perception with respect to signaling leading to root hair deformation and nodule primordium development versus infection thread formation and rhizobial entry.