Neptunia natans is a unique aquatic legume indigenous to tropical and sub-tropical regions and is nodulated symbiotically by rhizobia using an unusual infection process unlike any previously described. Previously, isolates of neptunia-nodulating rhizobia from Senegal were characterized as Allorhizobium undicola. Here we report on a different group of neptunia-nodulating rhizobia isolated from India. Sequencing of the 16S rDNA gene from two of these Indian isolates (strains J1T and J2) show that they belong in the genus Devosia rather than Allorhizobium. Currently, the only described Devosia species is D. riboflavina (family Hyphomicrobiaceae, order Rhizobiales). The complete 16S rDNA sequences of strains J1T and J2 are 95.9% homologous to the type strain, D. riboflavina LMG 2277T, suggesting that these neptunia-nodulating strains from India belong to a new Devosia species. This hypothesis was confirmed by further studies of polyphasic taxonomy (DNA-DNA hybridisation, TP-RAPD patterns, SDS-PAGE of cellular proteins, 16S rDNA RFLP patterns, carbon source utilisation, cellular fatty acid analysis and other phenotypic characterisations), all of which support the proposal that these neptunia-nodulating strains constitute a new Devosia species, which we name Devosia neptuniae sp. nov. These gram negative, strictly aerobic short rods are motile by a subpolar flagellum, positive for catalase, oxidase, urease and beta-galactosidase, can utilise several carbohydrates (but not organic acids) as carbon sources and contain C18:0 3-OH, cis-7 C18:1 11-methyl and cis-7 C18:1 as their major cellular fatty acids. Unlike D. riboflavina, the longer-chain C24:1 3-OH and C26:1 3-OH hydroxy fatty acids are not detected. The type strain of D. neptuniae is LMG 21357T (CECT 5650T). Assignment of this new taxon represents the fourth example in the literature of a non-rhizobial genus of bacteria capable of forming a bonafide dinitrogen-fixing root-nodule symbiosis with legume plants.