Vibrio cholerae are natural inhabitants of specific aquatic environments. Strains not belonging to serogroups O1 and O139 are usually unable to produce cholera toxin and cause cholera. However, non-toxigenic V. cholerae (NTVC) are able to cause a variety of mild-to-severe human infections (via seafood consumption or recreational activities). The number of unreported cases is considered substantial, as NTVC infections are not notifiable and physicians are mostly unaware of this pathogen. In the northern hemisphere, NTVC infections have been reported to increase due to global warming. In Eastern Europe, climatic and geological conditions favour the existence of inland water-bodies harbouring NTVC. We thus investigated the occurrence of NTVC in nine Serbian natural and artificial lakes and ponds, many of them used for fishing and bathing. With the exception of one highly saline lake, all investigated water-bodies harboured NTVC, ranging from 5.4 × 101 to 1.86 × 104 CFU and 4.5 × 102 to 5.6 × 106 genomic units per 100 ml. The maximum values observed were in the range of bathing waters in other countries, where infections have been reported. Interestingly, 7 out of 39 fully sequenced presumptive V. cholerae isolates were assigned as V. paracholerae, a recently described sister species of V. cholerae. Some clones and sublineages of both V. cholerae and V. paracholerae were shared by different environments indicating an exchange of strains over long distances. Important pathogenicity factors such as hlyA, toxR, and ompU were present in both species. Seasonal monitoring of ponds/lakes used for recreation in Serbia is thus recommended to be prepared for potential occurrence of infections promoted by climate change-induced rise in water temperatures.