BACKGROUND: Rapid diagnostic tests for malaria (mRDTs) have been scaled-up widely across Africa. The PRIME study evaluated an intervention aiming to improve fever case management using mRDTs at public health centers in Uganda. METHODS: A cluster-randomized trial was conducted from 2010-13 in Tororo, a high malaria transmission setting. Twenty public health centers were randomized in a 1:1 ratio to intervention or control. The intervention included training in health center management, fever case management with mRDTs, and patient-centered services; plus provision of mRDTs and artemether-lumefantrine (AL) when stocks ran low. Three rounds of Interviews were conducted with caregivers of children under five years of age as they exited health centers (N = 1400); reference mRDTs were done in children with fever (N = 1336). Health worker perspectives on mRDTs were elicited through semi-structured questionnaires (N = 49) and in-depth interviews (N = 10). The primary outcome was inappropriate treatment of malaria, defined as the proportion of febrile children who were not treated according to guidelines based on the reference mRDT. FINDINGS: There was no difference in inappropriate treatment of malaria between the intervention and control arms (24.0% versus 29.7%, adjusted risk ratio 0.81 [95% CI: 0.56, 1.17] p = 0.24). Most children (76.0%) tested positive by reference mRDT, but many were not prescribed AL (22.5% intervention versus 25.9% control, p = 0.53). Inappropriate treatment of children testing negative by reference mRDT with AL was also common (31.3% invention vs 42.4% control, p = 0.29). Health workers appreciated mRDTs but felt that integrating testing into practice was challenging given constraints on time and infrastructure. CONCLUSIONS: The PRIME intervention did not have the desired impact on inappropriate treatment of malaria for children under five. In this high transmission setting, use of mRDTs did not lead to the reductions in antimalarial prescribing seen elsewhere. Broader investment in health systems, including infrastructure and staffing, will be required to improve fever case management.