To allow rhizobial infection of legume roots, plant cell walls must be locally degraded for plant-made infection threads (ITs) to be formed. Here we identify a Lotus japonicus nodulation pectate lyase gene (LjNPL), which is induced in roots and root hairs by rhizobial nodulation (Nod) factors via activation of the nodulation signaling pathway and the NIN transcription factor. Two Ljnpl mutants produced uninfected nodules and most infections arrested as infection foci in root hairs or roots. The few partially infected nodules that did form contained large abnormal infections. The purified LjNPL protein had pectate lyase activity, demonstrating that this activity is required for rhizobia to penetrate the cell wall and initiate formation of plant-made infection threads. Therefore, we conclude that legume-determined degradation of plant cell walls is required for root infection during initiation of the symbiotic interaction between rhizobia and legumes.