Shortly after Kenya introduced artemether-lumefantrine (AL) for first-line treatment of uncomplicated malaria, we conducted a pre-post cluster randomized controlled trial to assess the effect of providing malaria rapid diagnostic tests (RDTs) on recommended treatment (patients with malaria prescribed AL) and overtreatment (patients without malaria prescribed AL) in outpatients >/= 5 years old. Sixty health facilities were randomized to receive either RDTs plus training, guidelines, and supervision (TGS) or TGS alone. Of 1,540 patients included in the analysis, 7% had uncomplicated malaria. The provision of RDTs coupled with TGS emphasizing AL use only after laboratory confirmation of malaria reduced recommended treatment by 63%-points (P = 0.04), because diagnostic test use did not change (-2%-points), but health workers significantly reduced presumptive treatment with AL for patients with a clinical diagnosis of malaria who did not undergo testing (-36%-points; P = 0.03). Health workers generally adhered to RDT results when prescribing AL: 88% of RDT-positive and 9% of RDT-negative patients were treated with AL, respectively. Overtreatment was low in both arms and was not significantly reduced by the provision of RDTs (-12%-points, P = 0.30). RDTs could potentially improve malaria case management, but we urgently need to develop more effective strategies for implementing guidelines before large scale implementation.