Reliable malaria related mortality data is important for planning appropriate interventions. However, there is scarce information on the pattern of malaria related mortality in epidemic prone districts of Tanzania. This study was carried out to determine malaria related mortality and establish its trend change over time in both epidemic and non-epidemic areas of Muleba District of north-western Tanzania. A verbal autopsy survey was conducted to obtain data on all deaths of individuals who died in six randomly selected villages from 1997 to 2006. Relatives of the deceased were interviewed using a standardized questionnaire. Communicable diseases accounted for about two thirds (61.9%) of deaths among ≥5 years individuals and 84.8% in ≤5 years. Non-communicable diseases accounted for 28.9% and 14.1% deaths in ≥5 years and ≤5 years, respectively. Malaria was the leading cause of deaths in all age groups (40.3%) and among children