Legumes have a symbiotic relationship with soil bacteria known as rhizobia, which induce the formation of a nitrogen-fixing nodules in the host. This symbiotic process includes Nod factor recognition and signaling, rhizobial infection, nodule formation, and establishment of functional (nitrogen-fixing) symbiosis. Genetic screens in model legumes Medicago truncatula and Lotus japonicus have identified symbiotic mutants that are blocked at different stages in the legume-rhizobium interaction. An early symbiotic signal transduction pathway is established that contains Nod factor recognition, signal transduction, and transcriptional response. In this review, we survey recent progress in understanding these aspects of the interaction.