Dioscorea sansibarensis is a monocot species of inedible yam native of tropical Africa and Madagascar. Leaves of D. sansibarensis feature prominent acumen glands that are densely colonized by bacteria. We describe here the isolation and characterization of bacteria from leaf glands of D. sansibarensis specimens obtained from various botanical gardens. Phylogenetic and phenotypic characterizations indicate that the isolates belong to a novel genus and species of the Alcaligenaceae family for which we propose the name Orrella dioscoreae gen. nov. sp. nov., with type strain LMG 29303(T) [=CIP 111009(T)]. Strains isolated from different plants show limited phylogenetic and phenotypic diversity, indicating specific and tight association of the bacteria with the host plant. The analysis of the draft genome of strain LMG 29303T reveals features consistent with a recently evolved plant-associated lifestyle