Cholera is on the rise globally, especially epidemic cholera which is characterized by intermittent and unpredictable outbreaks that punctuate periods of regional disease fade-out. These epidemic dynamics remain however poorly understood. Here we examine records for epidemic cholera over both contemporary and historical timelines, from Africa (1990-2006) and former British India (1882-1939). We find that the frequency distribution of outbreak size is fat-tailed, scaling approximately as a power-law. This pattern which shows strong parallels with wildfires is incompatible with existing cholera models developed for endemic regions, as it implies a fundamental role for stochastic transmission and local depletion of susceptible hosts. Application of a recently developed forest-fire model indicates that epidemic cholera dynamics are located above a critical phase transition and propagate in similar ways to aggressive wildfires. These findings have implications for the effectiveness of control measures and the mechanisms that ultimately limit the size of outbreaks.