Background The scale-up of malaria rapid diagnostic tests (RDTs) is intended to improve case management of fever and targeting of artemisinin-based combination therapy. Habitual presumptive treatment has hampered these intentions, suggesting a need for strategies to support behaviour change. We aimed to assess the introduction of RDTs when packaged with basic or enhanced clinician training interventions in Cameroon. Methods We did a three-arm, stratified, cluster-randomised trial at 46 public and mission health facilities at two study sites in Cameroon to compare three approaches to malaria diagnosis. Facilities were randomly assigned by a computer program in a 9:19:19 ratio to current practice with microscopy (widely available, used as a control group); RDTs with a basic (1 day) clinician training intervention; or RDTs with an enhanced (3 days) clinician training intervention. Patients (or their carers) and fieldworkers who administered surveys to obtain outcome data were masked to study group assignment. The primary outcome was the proportion of patients treated in accordance with WHO malaria treatment guidelines, which is a composite indicator of whether patients were tested for malaria and given appropriate treatment consistent with the test result. All analyses were by intention to treat. This study is registered at ClinicalTrials.gov, number NCT01350752. Findings The study took place between June 7 and Dec 14, 2011. The analysis included 681 patients from nine facilities in the control group, 1632 patients from 18 facilities in the basic-training group, and 1669 from 19 facilities in the enhanced-training group. The proportion of patients treated in accordance with malaria guidelines did not improve with either intervention; the adjusted risk ratio (RR) for basic training compared with control was 1·04 (95% CI 0·53—2·07; p=0·90), and for enhanced training compared with control was 1·17 (0·61—2·25; p=0·62). Inappropriate use of antimalarial drugs after a negative test was reduced from 84% (201/239) in the control group to 52% (413/796) in the basic-training group (unadjusted RR 0·63, 0·28—1·43; p=0·25) and to 31% (232/759) in the enhanced-training group (0·29, 0·11—0·77; p=0·02). Interpretation Enhanced clinician training, designed to translate knowledge into prescribing practice and improve quality of care, has the potential to halve overtreatment in public and mission health facilities in Cameroon. Basic training is unlikely to be sufficient to support the behaviour change required for the introduction of RDTs. Funding ACT Consortium (Bill & Melinda Gates Foundation).