The bacterium causing cholera, Vibrio cholerae, is essentially a marine organism and its ecological dynamics have been linked to oceanographic conditions and climate. We used autoregressive models with external inputs to identify potential relationships between the number of cholera cases in the coastal regions of mainland Tanzania with climatic and environmental indices (maximum air temperature, sea surface temperature, wind speed and chlorophyll a). Results revealed that, between 2004 and 2010, coastal regions of mainland Tanzania inhabited by approximately 21% of the total population accounted for approximately 50% of the cholera cases and 40% of the total mortality. Significant co-variations were found between seasonally adjusted cholera cases and coastal ocean chlorophyll a and, to some degree, sea surface temperature, the outbreaks lagging behind by one to four months. Cholera cases in Dar es Salaam were also weakly related to the Indian Ocean Dipole Mode Index, lagging by five months, suggesting that it may be possible to predict cholera outbreaks for Dar es Salaam this period ahead. The results also suggest that the severity of cholera in coastal regions can be predicted by ocean conditions and that longer-term environmental and climate parameters may be used to predict cholera outbreaks along the coastal regions.