Following an interaction with rhizobial soil bacteria, legume plants are able to form a novel organ, termed the root nodule. This organ houses the rhizobial microsymbionts, which perform the biological nitrogen fixation process resulting in the incorporation of ammonia into plant organic molecules. Recent advances in genomics have opened exciting new perspectives in this field by providing the complete gene inventory of two rhizobial microsymbionts. The complete genome sequences of Mesorhizobium loti, the symbiont of several Lotus species, and Sinorhizobium meliloti, the symbiont of alfalfa, were determined and annotated in detail. For legume macrosymbionts, expressed sequence tag projects and expression analyses using DNA arrays in conjunction with proteomics approaches have identified numerous genes involved in root nodule formation and nitrogen fixation. The isolation of legume genes by tagging or positional cloning recently allowed the identification of genes that control the very early steps of root nodule organogenesis.