The establishment of symbioses between eukaryotic hosts and bacterial symbionts in nature is a dynamic process. The formation of such relationships depends on the life history of both partners. Bacterial symbionts of amoebae may have unique evolutionary trajectories to the symbiont lifestyle, because bacteria are typically ingested as prey. To persist after being eaten, bacteria must survive phagocytosis. In the social amoeba Dictyostelium discoideum, certain strains of Burkholderia bacteria are able to resist amoebal digestion and maintain a persistent relationship that includes carriage throughout the amoeba’s social cycle that culminates in spore formation. Some Burkholderia strains allow their host to carry other bacteria as food. This carried food is released in new environments in a trait called farming. To better understand the diversity and prevalence of Burkholderia symbionts and the traits they impart to their amoebae hosts, we first screened 700 natural isolates of D. discoideum and found 25% infected with Burkholderia. We next used a multilocus phylogenetic analysis and identified two independent transitions by Burkholderia to the symbiotic lifestyle. Finally, we tested the ability of 38 strains of Burkholderia, from D. discoideum and as well as strains isolated from other sources, for traits relevant to symbiosis in D. discoideum. Only D. discoideum native isolates belonging to the B. agricolaris, B. hayleyella, and B.bonniea species were able to form a persistent symbiotic association with D. discoideum. The Burkholderia Dictyostelium relationship provides a promising arena for further studies of the pathway to symbiosis in a unique system.