Vibrio cholerae is a Gram-negative bacterium found in aquatic environments and is the aetiological agent of cholera, characterized by acute watery diarrhoea and severe dehydration. Cholera presents a significant global health burden of an estimated 1.3-5 million annual cases, with the current pandemic caused by a toxigenic lineage of the O1 El Tor biotype called seventh pandemic El Tor (7PET) that is still ongoing. Whilst it is known that non-7PET lineages can cause sporadic disease, little is known about the transmission of these non-epidemic lineages. Thirty-four V. cholerae isolates were obtained from travellers returning from Indonesia to Australia between 2005 and 2017. These were whole genome sequenced, placed into a global phylogenetic context with 883 isolates, and screened for known genes associated with antimicrobial resistance and virulence. This analysis revealed that 30 isolates fell within non-7PET lineages and four within the 7PET lineage. Both 7PET and non-7PET isolates carried genes for resistance to antibiotics that are commonly used in cholera treatment such as tetracyclines and fluoroquinolones. Diverse virulence factors were also present in non-7PET isolates, with two isolates notably carrying toxin-coregulated pilus genes, which are primarily responsible for intestinal colonization in 7PET V. cholerae. This study demonstrates the role of travel in long-range carriage of epidemic and non-epidemic lineages of V. cholerae, and how sentinel travel surveillance can enrich our knowledge of V. cholerae diversity, reveal new biology about the spread of diverse lineages with differing disease potential and illuminate disease presence in endemic regions with limited surveillance data.