Background When replacing failing drugs for malaria with more effective drugs, an important step towards reducing the malaria burden is that health workers (HW) prescribe drugs according to evidence-based guidelines. Past studies have shown that HW commonly do not follow guidelines, yet few studies have explored with appropriate methods why such practices occur. Methods We analysed data from a survey of government health facilities in four Kenyan districts in which HW consultations were observed, caretakers and HW were interviewed, and health facility assessments were performed. The analysis was limited to children 2–59 months old with uncomplicated malaria. Treatment was defined as recommended (antimalarial recommended by national guidelines), a minor error (effective, but non-recommended antimalarial), or inappropriate (no effective antimalarial). Results We evaluated 1006 consultations performed by 135 HW at 81 facilities: 567 children received recommended treatment, 314 had minor errors, and 125 received inappropriate treatment (weighted percentages: 56.9%, 30.4%, and 12.7%). Multivariate logistic regression analysis revealed that programmatic interventions such as in-service malaria training, provision of guidelines and wall charts, and more frequent supervision were significantly associated with better treatment quality. However, neither in-service training nor possession of the guideline document showed an effect by itself. More qualified HW made more errors: both major and minor errors (but generally more minor errors) when second-line drugs were in stock, and more major errors when second-line drugs were not in stock. Child factors such as age and a main complaint of fever were also associated with treatment quality. Conclusions Our results support the use of several programmatic strategies that can redress HW deficiencies in malaria treatment. Targeted cost-effectiveness trials would help refine these strategies and provide more precise guidance on affordable and effective ways to strengthen and maintain HW practices.