Vibrio vulnificus is a ubiquitous estuarine microorganism but causes fatal systemic infections in immunocompromised humans, cultured eels or shrimps. An extracellular metalloprotease VVP/VvpE has been reported to be a potential virulence factor of the bacterium; however, a few strains isolated from a diseased eel or shrimp were recently found to produce a serine protease termed VvsA, but not VVP/VvpE. In the present study, we found that these strains had lost the 80 kb genomic region including the gene encoding VVP/VvpE. We also purified VvsA from the culture supernatant through ammonium sulfate fractionation, gel filtration and ion-exchange column chromatography, and the enzyme was demonstrated to be a chymotrypsin-like protease, as well as those from some vibrios. The gene vvsA was shown to constitute an operon with a downstream gene vvsB, and several Vibrio species were found to have orthologues of vvsAB. These findings indicate that the genes vvp/vvpE and vvsAB might be mobile genetic elements.