Background: Tanzania ranks number four in the world (after Nigeria, Democratic Republic of Congo and India) with prevalence of SCD being 6 per 1000 live births (Piel et al, 2013). Sickle cell trait (HbS) has been associated with protection against severe, life-threatening Plasmodium falciparum malaria, which is an endemic disease in Sub Saharan countries with 90% of global malaria burden (Enevold et al., 2008). Objectives: To determine the prevalence, distribution between age and sex and association between HbS genotype and Plasmodium falciparum malarial infection among children aged 6 months – 5 years in Handeni district, Tanga, Northeastern Tanzania. Methodology: In a cross-sectional study of 311 children less than five years of age, associations between clinical malaria and HbS was evaluated between March and June 2016 in two villages in Handeni, Tanga. Hb variants were determined by DNA PCR. Blood smears were stained with Giemsa and parasite densities were determined microscopically. Results: The prevalence of clinical malaria among the enrolled children was 14.8%. The frequencies of the Hb variants were 79.4%, 20.3%, 0.3% respectively for HbAA, HbAS and HbSS. In Multivariate regression analysis, children with the HbAS genotype had 80% lower risk of malaria infection compared to those with HbAA genotype (OR=0.2, 95% CI: 0.06–0.66, p=0.01). The distribution of HbS in Handeni was 20.3% (63/311) in all children, among those 52.4% (33/63) were males, 77.8% (49/63) of the children with HbS aged between 12-60 months. Also 11.1% (7/63) of the children with HbS had clinical malaria. Conclusion: These results confirm previous findings showing a protective effect of sickle cell trait on clinical malaria. As millions of people are exposed to malaria annually, there is a need to continually explore all possible associations that red cell polymorphisms may have with disease susceptibility or protection when designing malaria intervention programs against this deadly disease. Recommendations: Among other recommendations, the researcher urges a need to build capacity among pediatricians in our setting to ensure effective management of children with sickle cell trait. Also larger studies involving other Hb variants like HbAC, G6PD variants and α-thalassaemia in order to observe their protection mechanisms against malaria.