We report the complete sequence of two novel plasmids, pSDH-1 and pSDH-2, isolated from clinical Vibrio cholerae non-O1/non-O139 during the early phase of the 2010 Haitian cholera epidemic. Plasmids were revealed by employing single-cell genomics and their genome content suggests self-mobilization and, for pSDH-2, a toxin-antitoxin system for plasmid stabilization was identified. The putative origin of replication of pSDH-2 was mapped suggesting it replicates following the ColE1 model of plasmid replication. pSDH-1 and pSDH-2 were widespread among environmental V. cholerae non-O1/non-O139 with variable prevalence in four Haitian Departments. pSDH-2 was the most common element, either alone or with pSDH-1. The two plasmids detection adds to the composite scenario of mobile genetic elements observed in V. cholerae in Haiti. The role these small cryptic plasmids circulating in Vibrio spp. play in bacterial fitness or pathogenicity merits further investigation.