Vibrio parahaemolyticus is an important human pathogen whose transmission is associated with the consumption of contaminated seafood. There is a growing public health concern due to the emergence of a pandemic strain causing severe outbreaks worldwide. Many questions remain unanswered regarding the evolution and population structure of V. parahaemolyticus. In this work, we describe a multilocus sequence typing (MLST) scheme for V. parahaemolyticus based on the internal fragment sequences of seven housekeeping genes. This MLST scheme was applied to 100 V. parahaemolyticus strains isolated from geographically diverse clinical (n = 37) and environmental (n = 63) sources. The sequences obtained from this work were deposited and are available in a public database (http://pubmlst.org/vparahaemolyticus). Sixty-two unique sequence types were identified, and most (50) were represented by a single isolate, suggesting a high level of genetic diversity. Three major clonal complexes were identified by eBURST analysis. Separate clonal complexes were observed for V. parahaemolyticus isolates originating from the Pacific and Gulf coasts of the United States, while a third clonal complex consisted of strains belonging to the pandemic clonal complex with worldwide distribution. The data reported in this study indicate that V. parahaemolyticus is genetically diverse with a semiclonal population structure and an epidemic structure similar to that of Vibrio cholerae. Genetic diversity in V. parahaemolyticus appears to be driven primarily by frequent recombination rather than mutation, with recombination ratios estimated at 2.5:1 and 8.8:1 by allele and site, respectively. Application of this MLST scheme to more V. parahaemolyticus strains and by different laboratories will facilitate production of a global picture of the epidemiology and evolution of this pathogen.