The genetic diversity of Vibrio vulnificus isolates from clinical and environmental sources originating from the Baltic Sea region was evaluated by multilocus sequence typing (MLST), and possible relationships between MLST clusters, potential genotypic and phenotypic traits associated with pathogenicity, and source of isolation were investigated. The studied traits included genotyping of polymorphic loci (16S rRNA, vcg, and pilF), presence/absence of potential virulence genes, including nanA, nab, and genes of pathogenicity regions, metabolic features, hemolytic activity, resistance to human serum, and cytotoxicity to human intestinal cells. MLST generated 35 (27 new) sequence types and divided the 53 isolates (including four reference strains) into two main clusters, with cluster I containing biotype 1 and 2 isolates of mainly environmental origin and cluster II containing biotype 1 isolates of mainly clinical origin. Cluster II isolates were further subdivided into two branches. Branch IIB included isolates from recent cases of wound infections that were acquired at the German Baltic Sea coastline between 2010 and 2011 and isolates from seawater samples of the same regions isolated between 1994 and 2010. Comparing the MLST data with the results of genotyping and phenotyping showed that strains of MLST cluster II possess a number of additional pathogenicity-associated traits compared to cluster I strains. Rapid microbiological methods such as matrix-assisted laser desorption ionization-time of flight (MALDI-TOF) mass spectrometry combined with typing of selected virulence-associated traits (e.g., serum resistance, mannitol fermentation, nanA, and pathogenicity region XII) could be used for risk assessment purposes regarding V. vulnificus strains isolated from the Baltic Sea region.