Gram-negative soil bacteria (rhizobia) within the Rhizobiaceae phylogenetic family (alpha-proteobacteria) have the unique ability to infect and establish a nitrogen-fixing symbiosis on the roots of leguminous plants. This symbiosis is of agronomic importance, reducing the need for nitrogen fertilizer for agriculturally important plants (e.g. soybean and alfalfa). The establishment of the symbiosis involves a complex interplay between host and symbiont, resulting in the formation of a novel organ, the nodule, which the bacteria colonize as intracellular symbionts. This review focuses on the most recent discoveries relating to how this symbiosis is established. Two general developments have contributed to the recent explosion of research progress in this area: first, the adoption of two genetic model legumes, Medicago truncatula and Lotus japonicus, and second, the application of modern methods in functional genomics (e.g. transcriptomic, proteomic and metabolomic analyses).