Cholera is a water-borne infectious disease that affects 1.3 to 4 million people, with 21,000 to 143,000 reported fatalities each year worldwide. Outbreaks are devastating to affected communities and their prospects for development. The key to support preparedness and public health response is the ability to forecast cholera outbreaks with sufficient lead time. How Vibrio cholerae survives in the environment outside a human host is an important route of disease transmission. Thus, identifying the environmental and climate drivers of these pathogens is highly desirable. Here, we elucidate for the first time a mechanistic link between climate variability and cholera (Satellite Water Marker; SWM) index in the Bengal Delta, which allows us to predict cholera outbreaks up to two seasons earlier. High values of the SWM index in fall were associated with above-normal summer monsoon rainfalls over northern India. In turn, these correlated with the La Niña climate pattern that was traced back to the summer monsoon and previous spring seasons. We present a new multi-linear regression model that can explain 50% of the SWM variability over the Bengal Delta based on the relationship with climatic indices of the El Niño Southern Oscillation, Indian Ocean Dipole, and summer monsoon rainfall during the decades 1997-2016. Interestingly, we further found that these relationships were non-stationary over the multi-decadal period 1948-2018. These results bear novel implications for developing outbreak-risk forecasts, demonstrating a crucial need to account for multi-decadal variations in climate interactions and underscoring to better understand how the south Asian summer monsoon responds to climate variability.