Increased temperatures provide optimal conditions for pathogen survival, virulence and replication as well as increased opportunities for human-pathogen interaction. This paper examined the relationship between notifications of cryptosporidiosis and temperature in metropolitan and rural areas of Victoria, Australia between 2001-2009. A negative binomial regression model was used to analyse monthly average maximum and minimum temperatures, rainfall and the monthly count of cryptosporidiosis notifications. In the metropolitan area, a 1°C increase in monthly average minimum temperature of the current month was associated with a 22% increase in cryptosporidiosis notifications (IRR 1.22; 95% CI 1.13 – 1.31). In the rural area, a 1°C increase in monthly average minimum temperature, lagged by 3 months, was associated with a 9% decrease in cryptosporidiosis notifications (IRR 0.91; 95% CI 0.86 – 0.97). Rainfall was not associated with notifications in either area. These relationships should be considered when planning public health response to ecological risks as well as when developing policies involving climate change. Rising ambient temperature may be an early warning signal for intensifying prevention efforts, including appropriate education for pool users about cryptosporidiosis infection and management, which might become more important as temperatures are projected to increase as a result of climate change.