Abstract Background Many patients with suspected malaria in sub-Saharan Africa seek treatment from private providers, but this sector suffers from sub-standard medicine dispensing practices. To improve the quality of care received for presumptive malaria from the highly accessed private retail sector in western Kenya, subsidized pre-packaged artemether-lumefantrine (AL) was provided to private retailers, together with a one day training for retail staff on malaria diagnosis and treatment, job aids and community engagement activities. Methods The intervention was assessed using a cluster-randomized, controlled design. Provider and mystery-shopper cross-sectional surveys were conducted at baseline and eight months post-intervention to assess provider practices. Data were analysed based on cluster-level summaries, comparing control and intervention arms. Results On average, 564 retail outlets were interviewed per year. At follow-up, 43% of respondents reported that at least one staff member had attended the training in the intervention arm. The intervention significantly increased the percentage of providers knowing the first line treatment for uncomplicated malaria by 24.2% points (confidence interval (CI): 14.8%, 33.6%; adjusted p=0.0001); the percentage of outlets stocking AL by 31.7% points (CI: 22.0%, 41.3%; adjusted p=0.0001); and the percentage of providers prescribing AL for presumptive malaria by 23.6% points (CI: 18.7%, 28.6%; adjusted p=0.0001). Generally outlets that received training and job aids performed better than those receiving one or none of these intervention components. Conclusion Overall, subsidizing ACT and retailer training can significantly increase the percentage of outlets stocking and selling AL for the presumptive treatment of malaria, but further research is needed on strategies to improve the provision of counselling advice to retail customers.