Cholera caused by pathogenic Vibrio cholerae is still considered one of the major health problems in developing countries including those in Asia and Africa. Australia is known to have unique V. cholerae strains in Queensland waterways, resulting in sporadic cholera-like disease being reported in Queensland each year. We conducted virulence and antimicrobial genetic characterization of O1 and non-O1, non-O139 V. cholerae (NOVC) strains (1983 to 2020) from Queensland with clinical significance and compared these to environmental strains that were collected as part of a V. cholerae monitoring project in 2012 of Queensland waterways. In this study, 87 V. cholerae strains were analyzed where O1 ( = 5) and NOVC ( = 54) strains from Queensland and international travel-associated NOVC ( = 2) (61 in total) strains were sequenced, characterized, and compared with seven previously sequenced O1 strains and 18 other publicly available NOVC strains from Australia and overseas to visualize the genetic context among them. Of the 61 strains, three clinical and environmental NOVC serogroup strains had cholera toxin-producing genes, namely, the CTX phage (identified in previous outbreaks) and the complete pathogenicity island 1. Phylogenetic analysis based on core genome analysis showed more than 10 distinct clusters and interrelatedness between clinical and environmental V. cholerae strains from Australia. Moreover, 30 (55%) NOVC strains had the cholix toxin gene () while only 11 (20%) strains had the gene. In addition, 18 (34%) NOVC strains from Australia had the type three secretion system and discrete expression of type six secretion system genes. Interestingly, four NOVC strains from Australia and one NOVC strain from Indonesia had SXT, a mobile genetic element. Several strains were found to have beta-lactamase () and chloramphenicol acetyltransferase () genes. Our study suggests that Queensland waterways can harbor highly divergent V. cholerae strains and serve as a reservoir for various V. cholerae-associated virulence genes which could be shared among O1 and NOVC V. cholerae strains via mobile genetic elements or horizontal gene transfer. Australia has its own V. cholerae strains, both toxigenic and nontoxigenic, that are associated with cholera disease. This study aimed to characterize a collection of clinical and environmental NOVC strains from Australia to understand their virulence and antimicrobial resistance profile and to place strains from Australia in the genetic context of international strains. The findings from this study suggest the toxigenic V. cholerae strains in the Queensland River water system are of public health concern. Therefore, ongoing monitoring and genomic characterization of V. cholerae strains from the Queensland environment are important and would assist public health departments to track the source of cholera infection early and implement prevention strategies for future outbreaks. Understanding the genomics of V. cholerae could also inform the natural ecology and evolution of this bacterium in natural environments.