An aerobic, Gram-negative, rod-shaped bacterium with polar flagella, strain CC-AFH3(T), was isolated from an oil-contaminated site located in Kaohsiung county, Taiwan. Strain CC-AFH3(T) grew at 20-40 °C, pH 5.0-10.0 and <2 % (w/v) NaCl. 16S rRNA gene sequence analysis indicated that strain CC-AFH3(T) showed the greatest degree of similarity to Herbaspirillum soli SUEMI10(T) (96.5 %), H. aurantiacum SUEMI08(T) (96.3 %), H. canariense SUEMI03(T) (96.0 %), H. psychrotolerans PB1(T) (95.4 %) and members of other Herbaspirillum species (94.1-95.2 %), and lower similarity to members of other genera (<94 %). Phylogenetic analyses also positioned the novel strain in the genus Herbaspirillum as an independent lineage. The major fatty acids in strain CC-AFH3(T) were C10 : 0 3-OH, C12 : 0, C14 : 0 2-OH, C16 : 0, iso-C15 : 0 3-OH, C17 : 0 cyclo, C16 : 1ω7c/C16 : 1ω6c and C18 : 1ω7c/C18 : 1ω6c. The major polar lipids of strain CC-AFH3(T) were diphosphatidylglycerol, phosphatidylethanolamine, phosphatidylglycerol and phosphatidylcholine. The predominant quinone was ubiquinone 8 (Q-8) and the DNA G+C content was 63.4 mol%. On the basis of 16S rRNA gene sequence analysis in combination with physiological and chemotaxonomic data, strain CC-AFH3(T) represents a novel species in a new genus, for which we propose the name Noviherbaspirillum malthae gen. nov., sp. nov.; the type strain of Noviherbaspirillum malthae is CC-AFH3(T) ( = BCRC 80516(T) = JCM 18414(T)). We also propose the reclassification of Herbaspirillum soli, Herbaspirillum aurantiacum, Herbaspirillum canariense and 'Herbaspirillum psychrotolerans' as Noviherbaspirillum soli comb. nov. (type strain SUEMI10(T) = LMG 26149(T) = CECT 7840(T)), Noviherbaspirillum aurantiacum comb. nov. (type strain SUEMI08(T) = LMG 26150(T) = CECT 7839(T)), Noviherbaspirillum canariense comb. nov. (type strain SUEMI03(T) = LMG 26151(T) = CECT 7838(T)) and Noviherbaspirillum psychrotolerans comb. nov. (type strain PB1(T) = DSM 26001(T) = LMG 27282(T)), respectively. An emended description of Herbaspirillum seropedicae is also presented.