BACKGROUND: Verbal autopsy (VA) procedures can be used to estimate cause of death in settings with inadequate vital registries. However, the sensitivity of VA for determining malaria-specific mortality may be low, and may vary with transmission intensity. We assessed the diagnostic accuracy of VA procedures as compared to hospital medical records for determining cause of death in children under five in three different malaria transmission settings in Uganda, including Tororo (high), Kampala (medium), and Kisoro (low). METHODS AND FINDINGS: Caretakers of children who died in participating hospitals were interviewed using a standardized World Health Organization questionnaire. Medical records from the child's hospitalization were also reviewed. Causes of death based on the VA questionnaires and the medical records were assigned independently by physician reviewers and then compared. A total of 719 cases were included in the final analysis, 67 in Tororo, 600 in Kampala, and 52 in Kisoro. Malaria was classified as the underlying or contributory cause of death by review of medical records in 33 deaths in Tororo, 60 in Kampala, and 0 in Kisoro. The sensitivity of VA procedures for determining malaria deaths in Tororo was 61% (95% CI 44-78%) and 50% in Kampala (95% CI 37-63%). Specificity for determining malaria deaths in Tororo and Kampala was high (>88%), but positive predictive value varied widely, from 83% in Tororo to 34% in Kampala (difference 49%, 95% CI 31-67, p<0.001). The difference between the cause-specific mortality fraction for malaria as determined by VA procedures and medical records was -11% in Tororo, +5% in Kampala, and +14% in Kisoro. CONCLUSIONS: Our results suggest that these VA methods have an acceptable level of diagnostic accuracy for determining malaria deaths at the population level in high and medium transmission areas, but not in low transmission areas.