New variants of Vibrio cholerae O1 have appeared in different time-frames in various endemic regions, especially in Asia and Africa. Sixty-nine strains of V. cholerae O1 isolated in Zambia between 1996 and 2004 were investigated by various genotypic techniques to determine the lineage of virulence signatures and clonality. All strains were positive for Vibrio seventh pandemic Islands (VSP)-I and VSP-II and repeat toxin (RTX) gene clusters attesting their El Tor lineage. Interestingly, strains isolated in recent times (2003–2004) were identified as an altered variant (El Tor biotype that harbours El Tor type rstR but produce classical ctxB) that replaced completely the progenitor El Tor strains prevalent in 1996–1997. Recent altered variant strains differed from prototype El Tor strains isolated earlier in that these strains lacked two ORFs, VC0493 and VC0498, in the VSP-II region. PFGE analysis revealed two major clonal lineages in the strains; cluster A represented the strains isolated before 2003 and cluster B the altered strains isolated in 2003–2004. Cluster A was closely related to prototype El Tor reference strain isolated in Bangladesh in 1971. Cluster B was found to be matched with Bangladeshi altered strains but was different from the hybrid strains isolated from Mozambique and Bangladesh. This report provides important information on the genesis of altered strains of V. cholerae O1 isolated in Zambia and emphasizes the need for further studies to follow the trends of evolutionary changes.