Background Exclusive breastfeeding (EBF) is a simple and cost-effective intervention to improve child health and survival. Effective EBF has been estimated to avert 13% - 15% of under-five mortality and contribute to reduce mother to child transmission of HIV. The prevalence of EBF for infant less than six months is low in most developing countries, including Tanzania (50%). While the Tanzania Demographic Health Survey collects information on overall EBF prevalence, it does not evaluate factors influencing EBF. The aim of this paper was to determine the prevalence and predictors of exclusive breastfeeding in urban and rural areas in Kilimanjaro region. Methods A population-based cross-sectional study was conducted between June 2010 to March 2011 among women with infants aged 6–12 months in Kilimanjaro. Multi-stage proportionate to size sampling was used to select participants from all the seven districts of the region. A standardized questionnaire was used to collect socio-demographic, reproductive, alcohol intake, breastfeeding patterns and nutritional data during the interviews. Estimation on EBF was based on recall since birth. Multivariable logistic regression was used to obtain independent predictors of EBF. Results A total of 624 women participated, 77% (483) from rural areas. The prevalence of EBF up to six months in Kilimanjaro region was 20.7%, without significant differences in the prevalence of EBF up to six months between urban (22.7%) and rural areas (20.1%); (OR = 0.7, 95% CI 0.5,1.4). In multivariable analysis, advice on breastfeeding after delivery (Adjusted odds ratio, AOR = 2.6, 95% CI 1.5, 4.6) was positively associated with EBF up to six months. Compared to married/cohabiting and those who do not take alcohol, single mothers (AOR = 0.4, 95% CI 0.2, 0.9) and mothers who drank alcohol (AOR = 0.4, 95% CI 0.3, 0.7) had less odds to practice EBF up to six months. Conclusion Prevalence of EBF up to six months is still low in Kilimanjaro, lower than the national coverage of 50%. Strengthening of EBF counseling in all reproductive and child health clinics especially during antenatal and postnatal periods may help to improve EBF rates.