Leguminous plants (such as peas and soybeans) and rhizobial soil bacteria are symbiotic partners that communicate through molecular signaling pathways, resulting in the formation of nodules on legume roots and occasionally stems that house nitrogen-fixing bacteria. Nodule formation has been assumed to be exclusively initiated by the binding of bacterial, host-specific lipochito-oligosaccharidic Nod factors, encoded by the nodABC genes, to kinase-like receptors of the plant. Here we show by complete genome sequencing of two symbiotic, photosynthetic, Bradyrhizobium strains, BTAi1 and ORS278, that canonical nodABC genes and typical lipochito-oligosaccharidic Nod factors are not required for symbiosis in some legumes. Mutational analyses indicated that these unique rhizobia use an alternative pathway to initiate symbioses, where a purine derivative may play a key role in triggering nodule formation.