BACKGROUND: Surveillance data are essential for malaria control, but quality is often poor. The aim of the study was to evaluate the effectiveness of the novel combination of training plus an innovative quality improvement method-collaborative improvement (CI)-on the quality of malaria surveillance data in Uganda. METHODS: The intervention (training plus CI, or TCI), including brief in-service training and CI, was delivered in 5 health facilities (HFs) in Kayunga District from November 2015 to August 2016. HF teams monitored data quality, conducted plan-do-study-act cycles to test changes, attended periodic learning sessions, and received CI coaching. An independent evaluation was conducted to assess data completeness, accuracy, and timeliness. Using an interrupted time series design without a separate control group, data were abstracted from 156,707 outpatient department (OPD) records, laboratory registers, and aggregated monthly reports (MR) for 4 time periods: baseline-12 months, TCI scale-up-5 months; CI implementation-9 months; post-intervention-4 months. Monthly OPD register completeness was measured as the proportion of patient records with a malaria diagnosis with: (1) all data fields completed, and (2) all clinically-relevant fields completed. Accuracy was the relative difference between: (1) number of monthly malaria patients reported in OPD register versus MR, and (2) proportion of positive malaria tests reported in the laboratory register versus MR. Data were analysed with segmented linear regression modelling. RESULTS: Data completeness increased substantially following TCI. Compared to baseline, all-field completeness increased by 60.1%-points (95% confidence interval [CI]: 46.9-73.2%) at mid-point, and clinically-relevant completeness increased by 61.6%-points (95% CI: 56.6-66.7%). A relative - 57.4%-point (95% confidence interval: - 105.5, - 9.3%) change, indicating an improvement in accuracy of malaria test positivity reporting, but no effect on data accuracy for monthly malaria patients, were observed. Cost per additional malaria patient, for whom complete clinically-relevant data were recorded in the OPD register, was $3.53 (95% confidence interval: $3.03, $4.15). CONCLUSIONS: TCI improved malaria surveillance completeness considerably, with limited impact on accuracy. Although these results are promising, the intervention's effectiveness should be evaluated in more HFs, with longer follow-up, ideally in a randomized trial, before recommending CI for wide-scale use.