BACKGROUND: In Zanzibar, the Ministry of Health and partners accelerated malaria control from September 2003 onwards. The impact of the scale-up of insecticide-treated nets (ITN), indoor-residual spraying (IRS) and artemisinin-combination therapy (ACT) combined on malaria burden was assessed at six out of seven in-patient health facilities. METHODS: Numbers of outpatient and inpatient cases and deaths were compared between 2008 and the pre-intervention period 1999-2003. Reductions were estimated by segmented log-linear regression, adjusting the effect size for time trends during the pre-intervention period. RESULTS: In 2008, for all age groups combined, malaria deaths had fallen by an estimated 90% (95% confidence interval 55-98%)(p < 0.025), malaria in-patient cases by 78% (48-90%), and parasitologically-confirmed malaria out-patient cases by 99.5% (92-99.9%). Anaemia in-patient cases decreased by 87% (57-96%); anaemia deaths and out-patient cases declined without reaching statistical significance due to small numbers. Reductions were similar for children under-five and older ages. Among under-fives, the proportion of all-cause deaths due to malaria fell from 46% in 1999-2003 to 12% in 2008 (p < 0.01) and that for anaemia from 26% to 4% (p < 0.01). Cases and deaths due to other causes fluctuated or increased over 1999-2008, without consistent difference in the trend before and after 2003. CONCLUSIONS: Scaling-up effective malaria interventions reduced malaria-related burden at health facilities by over 75% within 5 years. In high-malaria settings, intensified malaria control can substantially contribute to reaching the Millennium Development Goal 4 target of reducing under-five mortality by two-thirds between 1990 and 2015.