Vibrio parahaemolyticus is a common marine bacterium and a leading cause of seafood-borne bacterial gastroenteritis worldwide. Although this bacterium has been the subject of much research, the population structure of cold-water populations remains largely undescribed. We present a broad phylogenetic analysis of clinical and environmental V. parahaemolyticus originating largely from the Pacific Northwest coast of the United States. Repetitive extragenic palindromic PCR (REP-PCR) separated 167 isolates into 39 groups and subsequent multilocus sequence typing (MLST) separated a subset of 77 isolates into 24 sequence types. The Pacific Northwest population exhibited a semi-clonal structure attributed to an environmental clade (ST3, N = 17 isolates) clonally related to the pandemic O3:K6 complex and a clinical clade (ST36, N = 20 isolates) genetically related to a regionally endemic O4:K12 complex. Further, the identification of at least five additional clinical sequence types (i.e., ST43, 50, 65, 135 and 417) demonstrates that V. parahaemolyticus gastroenteritis in the Pacific Northwest is polyphyletic in nature. Recombination was evident as a significant source of genetic diversity and in particular, the recA and dtdS alleles showed strong support for frequent recombination. Although pandemic-related illnesses were not documented during the study, the environmental occurrence of the pandemic clone may present a significant threat to human health and warrants continued monitoring. It is evident that V. parahaemolyticus population structure in the Pacific Northwest is semi-clonal and it would appear that multiple sequence types are contributing to the burden of disease in this region.