Although malnutrition and malaria co-occur among individuals and populations globally, effects of nutritional status on risk for parasitemia and clinical illness remain poorly understood. We investigated associations between Plasmodium falciparum infection, nutrition, and food security in a cross-sectional survey of 365 Batwa pygmies in Kanungu District, Uganda in January of 2013. We identified 4.1% parasite prevalence among individuals over 5 years old. Severe food insecurity was associated with increased risk for positive rapid immunochromatographic test outcome (adjusted relative risk [ARR] = 13.09; 95% confidence interval [95% CI] = 2.23-76.79). High age/sex-adjusted mid-upper arm circumference was associated with decreased risk for positive test among individuals who were not severely food-insecure (ARR = 0.37; 95% CI = 0.19-0.69). Within Batwa pygmy communities, where malnutrition and food insecurity are common, individuals who are particularly undernourished or severely food-insecure may have elevated risk for P. falciparum parasitemia. This finding may motivate integrated control of malaria and malnutrition in low-transmission settings.