The bacterium causing cholera, Vibrio cholerae, is a marine organism and coastal waters are important reservoirs of the organism. There are more than 200 serogroups of V. cholerae, of which serogroups O1 and O139 are known to be the causative agent of the cholera. The main virulent factor in V. cholerae is cholera toxin gene (ctx) that is found from the epidemic O1 and O139 strains, but may also be found in some strains other than O1 and O139 (non-O1 and non-O139). In this study, 48 V. cholerae strains isolated from three estuaries of Tanzania and 20 stool isolates were characterized in terms of their serogroups and possession of ctx gene and then compared using two PCR based fingerprinting methods: Enterobacterial repetitive intergenic consensus (ERIC) sequences and repetitive extragenic palindromic (REP) sequences. All the stool isolates and twelve of the environmental isolates belonged to serogroup O1 while the remaining 36 environmental isolates were defined as non-O1/O139. The entire stool isolates and 21 of the environmental isolates had the cholera toxin gene (ctxA). Both ERIC and REP methods gave almost unique fingerprints for each strain and confirmed high genetic heterogeneity among the different cholera strains. Higher similarity was observed in REP-PCR (70-100%) than in ERIC-PCR (62-100%), indicating different discriminative power of these methods. Environmental isolates clustered together with clinical isolates at ≥90% similarity level suggesting their great potential of producing pathogenic strains that may be the causative agents for the frequent observed cholera outbreaks particularly along the coast.