During a survey of root-nodulating symbionts of Mimosoid species in the south-east region of Brazil, eight Paraburkholderia isolates were obtained from nodules of the legume species Piptadenia gonoacantha, either from the field or following a soil trapping method with the same plant host. 16S rRNA gene as well as recA and gyrB phylogenetic markers placed these strains in two new clades within the genus Burkholderia sensu lato. DNA-DNA hybridization values and analyses of average nucleotide identities of the whole genome sequence of selected strains in each clade (STM 7183 and STM 7296) showed that the two clades represented novel species of the genus Paraburkholderia. All eight isolates were further characterized using DNA base content determination, chemotaxonomic and biochemical profiling and symbiotic properties, which allowed to distinguish the novel species from known diazotrophic species of the genus Paraburkholderia. Based on genomic and phenotypic data, the names Paraburkholderia piptadeniae sp. nov. with type strain STM 7183T (=DSM 101189T=LMG 29163T) and Paraburkholderia ribeironis sp. nov. with type strain STM 7296T (=DSM 101188T=LMG 29351T) are proposed.