BACKGROUND: Malaria is a risk factor for invasive non-typhoidal Salmonella (NTS) infection in children. In the last 10 years, indices of malaria infection in The Gambia have fallen substantially. METHODS: We compared temporal trends of childhood malaria and NTS infection in two Gambian locations. In Fajara, on the coast, the incidence of NTS infection at three time points between 1979 and 2005 was compared to the percentage of malaria positive outpatient thick blood films and the percentage of admissions associated with malaria over time. In Basse, in the eastern part of the country, the incidence of NTS infection at three time points between 1989 and 2008 was compared to the prevalence of malaria parasitaemia at four time points between 1992 and 2008. RESULTS: The estimated incidence of NTS infection in Fajara fell from 60 (1979-1984) to 10 (2003-05) cases per 100,000 person years. The proportion of outpatients in Fajara with suspected malaria who were parasitaemic fell from 33% (1999) to 6% (2007) while the proportion of admissions associated with malaria fell from 14.5% (1999) to 5% (2007). In Basse, the estimated incidence of NTS infection fell from 105 (1989-1991) to 29 (2008) cases per 100,000 person years while the prevalence of malaria parasitaemia fell from 45% (1992) to 10% (2008). The incidence of pneumococcal bacteraemia in Fajara and Basse did not fall over the study period. CONCLUSIONS: These data support an association between malaria and NTS infection. Reductions in malaria infection may be associated with reduced rates of invasive childhood NTS infection.