This paper describes the development and application of multilocus sequencing typing (MLST) and multi-virulence locus sequencing typing (MVLST) methods in determining the genetic variation and relatedness of 43 Vibrio cholerae strains of different serogroups isolated from various sources in Malaysia. The MLST assay used six housekeeping genes (dnaE, lap, recA, gyrB, cat and gmd), while the MVLST assay incorporated three virulence genes (ctxAB, tcpA and tcpI) and three virulence-associated genes (hlyA, toxR and rtxA). Our data showed that the dnaE and rtxA genes were the most conserved genes in V. cholerae O1 strains. Among the 12 studied genes, transitional substitutions that led to silent mutations were observed in all, except for gmd and hlyA, while non-synonymous substitutions occurred more frequently in virulence and virulence-associated genes. Five V. cholerae O1 strains were found to be the El Tor variant O1 strains because they harboured the classical ctxB gene. In addition, the classical ctxB gene was also observed in O139 V. cholerae. A total of 29 MLST types were observed, and this assay could differentiate V. cholerae within the non-O1/non-O139 serogroups. A total of 27 MVLST types were obtained. MVLST appeared to be more discriminatory than MLST because it could differentiate V. cholerae strains from two different outbreaks and could separate the toxigenic from the non-toxigenic subtypes. Although the O1 V. cholerae strains were closely related, the combined MLST and MVLST analyses differentiated the strains isolated from different localities. In conclusion, sequence-based analysis in this study provided a better understanding of mutation points and the type of mutations in V. cholerae. The MVLST assay is useful to characterise O1 V. cholerae strains, while combined analysis may improve the discriminatory power and is suitable for the local epidemiological study of V. cholerae.