Vibrio cholerae is a natural inhabitant of many aquatic environments in the world. Biotypes harboring similar virulence-related gene clusters are the causative agents of epidemic cholera, but the majority of strains are harmless to humans. Since 1971, environmental surveillance for potentially pathogenic V. cholerae has resulted in the isolation of many strains from the Brazilian Amazon aquatic ecosystem. Most of these strains are from the non-O1/non-O139 serogroups (NAGs), but toxigenic O1 strains were isolated during the Latin America cholera epidemic in the region (1991-1996). A collection of environmental V. cholerae strains from the Brazilian Amazon belonging to pre-epidemic (1977-1990), epidemic (1991-1996), and post-epidemic (1996-2007) periods in the region, was analyzed. The presence of genes related to virulence within the species and the genetic relationship among the strains were studied. These variables and the information available concerning the strains were used to build a Bayesian multivariate dependency model to distinguish the importance of each variable in determining the others. Some genes related to the epidemic strains were found in environmental NAGs during and after the epidemic. Significant diversity among the virulence-related gene content was observed among O1 strains isolated from the environment during the epidemic period, but not from clinical isolates, which were analyzed as controls. Despite this diversity, these strains exhibited similar PFGE profiles. PFGE profiles were significant while separating potentially epidemic clones from indigenous strains. No significant correlation with isolation source, place or period was observed. The presence of the WASA-1 prophage significantly correlated with serogroups, PFGE profiles, and the presence of virulence-related genes. This study provides a broad characterization of the environmental V. cholerae population from the Amazon, and also highlights the importance of identifying precisely defined genetic markers such as the WASA-1 prophage for the surveillance of cholera.