BACKGROUND: Zambia was the first African country to change national antimalarial treatment policy to artemisinin-based combination therapy--artemether-lumefantrine. An evaluation during the early implementation phase revealed low readiness of health facilities and health workers to deliver artemether-lumefantrine, and worryingly suboptimal treatment practices. Improvements in the case-management of uncomplicated malaria two years after the initial evaluation and three years after the change of policy in Zambia are reported. METHODS: Data collected during the health facility surveys undertaken in 2004 and 2006 at all outpatient departments of government and mission facilities in four Zambian districts were analysed. The surveys were cross-sectional, using a range of quality of care assessment methods. The main outcome measures were changes in health facility and health worker readiness to deliver artemether-lumefantrine, and changes in case-management practices for children below five years of age presenting with uncomplicated malaria as defined by national guidelines. RESULTS: In 2004, 94 health facilities, 103 health workers and 944 consultations for children with uncomplicated malaria were evaluated. In 2006, 104 facilities, 135 health workers and 1125 consultations were evaluated using the same criteria of selection. Health facility and health worker readiness improved from 2004 to 2006: availability of artemether-lumefantrine from 51% (48/94) to 60% (62/104), presence of artemether-lumefantrine dosage wall charts from 20% (19/94) to 75% (78/104), possession of guidelines from 58% (60/103) to 92% (124/135), and provision of in-service training from 25% (26/103) to 41% (55/135). The proportions of children with uncomplicated malaria treated with artemether-lumefantrine also increased from 2004 to 2006: from 1% (6/527) to 27% (149/552) in children weighing 5 to 9 kg, and from 11% (42/394) to 42% (231/547) in children weighing 10 kg or more. In both weight groups and both years, 22% (441/2020) of children with uncomplicated malaria were not prescribed any antimalarial drug. CONCLUSION: Although significant improvements in malaria case-management have occurred over two years in Zambia, the quality of treatment provided at the point of care is not yet optimal. Strengthening weak health systems and improving the delivery of effective interventions should remain high priority in all countries implementing new treatment policies for malaria.