Optimizing quality of care for malaria and other febrile illnesses is a complex challenge of major public health importance. To evaluate the impact of an intervention aiming to improve malaria case management on the health of community children, a cluster-randomized trial was conducted from 2010-2013 in Tororo, Uganda, where malaria transmission is high. Twenty public health centers were included; 10 were randomized in a 1:1 ratio to intervention or control. Households within 2 km of health centers provided the sampling frame for the evaluation. The PRIME intervention included training in fever case management using malaria rapid diagnostic tests (mRDTs), patient-centered services, and health center management; plus provision of mRDTs and artemether-lumefantrine. Cross-sectional community surveys were conducted at baseline and endline (N = 8,766), and a cohort of children was followed for approximately 18 months (N = 992). The primary outcome was prevalence of anemia (hemoglobin < 11.0 g/dL) in children under 5 years of age in the final community survey. The intervention was delivered successfully; however, no differences in prevalence of anemia or parasitemia were observed between the study arms in the final community survey or the cohort. In the final survey, prevalence of anemia in children under 5 years of age was 62.5% in the intervention versus 63.1% in control (adjusted risk ratio = 1.01; 95% confidence interval = 0.91-1.13; P = 0.82). The PRIME intervention, focusing on training and commodities, did not produce the expected health benefits in community children in Tororo. This challenges common assumptions that improving quality of care and access to malaria diagnostics will yield health gains.