Background: Malaria is a major public health concern in Bangladesh and it is highly endemic in the Chittagong Hill Tracts where prevalence was 11.7% in 2007. One sub-district, Rajasthali, had a prevalence of 36%. Several interventions were introduced in early 2007 to control malaria. This study was undertaken to evaluate the impacts of these intensive early stage interventions on malaria in Bangladesh. This prevalence study assesses whether or not high malaria prevalence remains, and if so, which areas and individuals remain at high risk of infection. Methods and Principal Findings: A 2-stage cluster sampling technique was used to sample 1,400 of 5,322 (26.3%) households in Rajasthali, and screened using a rapid diagnostic test (Falci-vax). Overall malaria prevalence was 11.5%. The proportions of Plasmodium falciparum, Plasmodium vivax and infection with both species were 93.2%, 1.9% and 5.0%, respectively. Univariate, multivariate logistic regression, and spatial cluster analyses were performed separately. Sex, age, number of bed nets, forest cover, altitude and household density were potential risk factors. A statistically significant malaria cluster was identified. Significant differences among risk factors were observed between cluster and non-cluster areas. Conclusion and Significance: Malaria has significantly decreased within 2 years after onset of intervention program. Both aspects of the physical and social environment, as well as demographic characteristics are associated with spatial heterogeneity of risk. The ability to identify and locate these areas provides a strategy for targeting interventions during initial stages of intervention programs. However, in high risk clusters of transmission, even extensive coverage by current programs leaves transmission ongoing at reduced levels. This indicates the need for continued development of new strategies for identification and treatment as well as improved understanding of the patterns and determinants of parasitaemia.