Abstract Aim This study analysed the diversity and identity of the rhizobial symbionts of co-existing exotic and native legumes in a coastal dune ecosystem invaded by Acacia longifolia. Location An invaded coastal dune ecosystem in Portugal and reference bradyrhizobial strains from the Iberian Peninsula and other locations. Methods Symbiotic nitrogen-fixing bacteria were isolated from root nodules of plants of the Australian invasive Acacia longifolia and the European natives Cytisus grandiflorus, Cytisus scoparius and Ulex europaeus. Total DNA of each isolate was amplified by polymerase chain reaction (PCR) with the primer BOX A1R. Subsequent PCR-sequencing and phylogenetic analyses of the internal transcribed spacer region and the nifD and nodA genes were performed for all different strains. Results The four plant species analysed were nodulated by bacteria from three different Bradyrhizobium lineages, although most of the isolates belonged to the Bradyrhizobium japonicum lineage sensu lato. Ninety-five per cent of the bradyrhizobia isolated from A. longifolia, C. grandiflorus and U. europaeus in the invaded ecosystem had nifD and nodA genes of Australian origin. Seven isolates obtained in this study define a new distinctive nifD group of Bradyrhizobium from western and Mediterranean Europe. Main conclusions These results reveal the introduction of exotic bacteria with the invasive plant species, their persistence in the new geographical area and the nodulation of native legumes by rhizobia containing exotic symbiotic genes. The disruption of native mutualisms and the mutual facilitation of the invasive spread of the introduced plant and bradyrhizobia could constitute the first report of an invasional meltdown documented for a plant–bacteria mutualism.