Vibrio cholerae is the causative agent of cholera, a globally important human disease for at least 200 years. In 2009–2011, the first recorded cholera outbreak in Papua New Guinea (PNG) occurred. We conducted genetic and phenotypic characterization of 21 isolates of V. cholerae, with whole-genome sequencing conducted on 2 representative isolates. The PNG outbreak was caused by an atypical El Tor strain harbouring a tandem repeat of the CTX prophage on chromosome II. Whole-genome sequence data, prophage structural analysis and the absence of the SXT integrative conjugative element was indicative that the PNG isolates were most closely related to strains previously isolated in South-East and East Asia with affiliations to global wave 2 strains. This finding suggests that the cholera outbreak in PNG was caused by an exotic (nonendemic) strain of V. cholerae that originated in South-East Asia.