Plesiomonas shigelloides is an emerging pathogen that is widespread in the aquatic environment and is responsible for intestinal diseases and extraintestinal infections in humans and other animals. Virtually nothing is known about its genetic diversity, population structure, and evolution, which severely limits epidemiological control. We addressed these questions by developing a multilocus sequence typing (MLST) system based on five genes (fusA, leuS, pyrG, recG, and rpoB) and analyzing 77 epidemiologically unrelated strains from several countries and several ecological sources. The phylogenetic position of P. shigelloides within family Enterobacteriaceae was precisely defined by phylogenetic analysis of the same gene portions in other family members. Within P. shigelloides, high levels of nucleotide diversity (average percentage of nucleotide differences between strains, 1.49%) and genotypic diversity (64 distinct sequence types; Simpson's index, 99.7%) were found, with no salient internal phylogenetic structure. We estimated that homologous recombination in housekeeping genes affects P. shigelloides alleles and nucleotides 7 and 77 times more frequently than mutation, respectively. These ratios are similar to those observed in the naturally transformable species Streptococcus pneumoniae with a high rate of recombination. In contrast, recombination within Salmonella enterica, Escherichia coli, and Yersinia enterocolitica was much less frequent. P. shigelloides thus stands out among members of the Enterobacteriaceae. Its high rate of recombination results in a lack of association between genomic background and O and H antigenic factors, as observed for the 51 serotypes found in our sample. Given its robustness and discriminatory power, we recommend MLST as a reference method for population biology studies and epidemiological tracking of P. shigelloides strains.