Chronological analysis of 125 Vibrio cholerae O139 strains isolated during 1993-2005 in Kolkata revealed the prevalence of two new genotypes of cholera toxin (CT) and novel combinations of ctxB and rstR alleles resulting in variant CTX prophages. One of the new genotypes of ctxB, which first appeared in 1996 with the re-emerged V. cholerae O139 strains that had CTX Calcutta phage, was designated as genotype 4. In 1998, another new genotype, designated as genotype 5, was detected that prevailed mostly in CTX phages with El Tor rstR. The prototype El Tor CTX phage with genotype 3 gradually disappeared in O139, and since 2002 the predominant CTX prophages in O139 are Calcutta phages with genotype 4 and El Tor phages with genotype 5. Results showed that V. cholerae O139 strains of Kolkata, isolated over a decade, harboured CTX prophages in the large chromosome having no RS1 downstream of CTX prophage. During the course of its intermittent incidence over a decade, five types of O139 strains were detected based on CT genotypes. Such abrupt genetic changes in O139 strains might not favour its continued prevalence in human cases in Kolkata, India.