In facultative symbioses, only a fraction of hosts are associated with symbionts. Specific host and symbiont pairings may be the result of host-symbiont coevolution driven by reciprocal selection, or priority effects pertaining to which potential symbiont became associated with a host first. Distinguishing between these possibilities is important for understanding the evolutionary forces that affect facultative symbioses. We used the social amoeba Dictyostelium discoideum and its symbiont Paraburkholderia bonniea to determine whether ongoing coevolution affects which host-symbiont strain pairs naturally co-occur within a facultative symbiosis. Relative to other Paraburkholderia, including another symbiont of D. discoideum, P. bonniea features a reduced genome size that indicates a significant history of coevolution with its host. We hypothesized that ongoing host-symbiont coevolution would lead to higher fitness for naturally co-occurring (native) host and symbiont pairings compared to novel pairings. We show for the first time that P. bonniea symbionts can horizontally transmit to new amoeba hosts when hosts aggregate together during the social stage of their life cycle. Here we find evidence for a virulence-transmission trade-off without host specificity. Although symbiont strains were significantly variable in virulence and horizontal transmission rate, hosts and symbionts responded similarly to associations in native and novel pairings. We go on to identify candidate virulence factors in the genomes of P. bonniea strains that may contribute to variation in virulence. We conclude that ongoing coevolution is unlikely for D. discoideum and P. bonniea. The system instead appears to represent a stable facultative symbiosis in which naturally co-occurring P. bonniea host and symbiont pairings are the result of priority effects.