Abstract Cholera continues to be a serious public health issue in developing countries. We analyzed the epidemiological data of cholera from 1976 to 2013 in Shandong Province, an eastern coastal area of China. A total of 250 Vibrio cholerae isolates were selected for PCR analysis of virulence genes and pulsed-field gel electrophoresis (PFGE). The analysis of the virulence genes showed that the positive rates for tcpA and tcpI were the highest among strains from the southwest region, which had the highest incidence rate of cholera. Low positive rates for tcpA, tcpI and ctxAB among isolates from after 2000 may be an influencing factor contributing to the contemporary decline in cholera incidence rates. Spatiotemporal serotype shifts (Ogawa, Inaba, Ogawa, Inaba and O139) generally correlated with the variations in the PFGE patterns (PIV, PIIIc, PIa, PIIIb, PIIIa, PIb, and PII). O1 strains from different years or regions also had similar PFGE patterns, while O139 strains exclusively formed one cluster and differed from all other O1 strains. These data indicate that V. cholerae isolates in Shandong Province have continually undergone spatiotemporal changes. The serotype switching between Ogawa and Inaba originated from indigenous strains, while the emergence of serogroup O139 appeared to be unrelated to endemic V. cholerae O1 strains.