ABSTRACT: BACKGROUND: In Uganda, parasite-based diagnosis is recommended for every patient suspected to have malaria before prescribing anti-malarials. However, the majority of patients are still treated presumptively especially in low-level health units. The feasibility of implementing parasite-based diagnosis for uncomplicated malaria in rural health centres (HCs) was investigated with a view to recommending measures for scaling up the policy. METHODS: Thirty HCs were randomized to implement parasite-based diagnosis based on rapid diagnostic tests [RDTs] (n=10), blood microscopy (n=10) and presumptive diagnosis (control arm) (n=10). Feasibility was assessed by comparing the proportion of patients who received parasite-based diagnosis; with a positive malaria parasite-based diagnosis who received artemether-lumefantrine (AL); with a negative malaria parasite-based diagnosis who received AL; and patient waiting time. Clinicaltrials.gov: NCT00565071. RESULTS: 102,087 outpatients were enrolled. Patients were more likely to be tested in the RDT 44,565 (96.6%) than in microscopy arm 19,545 (60.9%) [RR: 1.59]. RDTs reduced patient waiting time compared to microscopy and were more convenient to health workers and patients. Majority 23,804 (99.7%) in presumptive arm were prescribed AL. All (100%) of patients who tested positive for malaria in RDT and microscopy arms were prescribed anti-malarials. Parasitological-based diagnosis significantly reduced AL prescription in RDT arm [RR: 0.62] and microscopy arm [RR: 0.72] compared to presumptive treatment. Among patients not tested in the two intervention arms, 12,044 (96.1%) in microscopy and 965 (61.6%) in RDT arm were treated with AL [RR: 1.56]. Overall 10,558 (29.4%) with negative results [5,110 (23.4%) in RDT and 5,448 (39.0%) in microscopy arms] were prescribed AL. CONCLUSION: It was more feasible to implement parasite-based diagnosis for malaria using RDT than with microscopy. A high proportion of patients with negative malaria results are still prescribed anti-malarials. There is need to increase access to parasite-based diagnosis where microscopy is used. In order to fully harness the benefits of parasitological confirmation of malaria, it is necessary to reduce the prescription of anti-malarials in negative patients.