Effective case management is central for malaria control, but not all of those affected by malaria have access to prompt, effective treatment. In Kenya, free malaria treatment has been implemented since 2006. However, questions remain regarding effective treatment. We conducted cross-sectional epidemiological and questionnaire surveys in four counties in western Kenya in 2004, 2010, and 2016, and antimalarial availability surveys in 2016. We found a significant decline in self-reported malaria cases and an improvement in knowledge of malaria prevention and treatment since 2004. Parasite prevalence declined significantly from 2004 to 2010; however, it has remained unchanged since then. Artemisinin-based combination therapies (ACTs) and sulfadoxine-pyrimethamine (SP) drugs were widely available everywhere. The proportion of ACT usage increased from none in 2004 to 48% and 69%, respectively, in 2010 and 2016, whereas SP drug usage declined from 88% in 2004 to 39% in 2010 and 27% in 2016. During the 2016 survey, non-intermittent preventive treatment in pregnancy use of SP was common (20.9% of all surveyed individual treatments). In 2004, 27.2% (168/617) of households sought hospital treatment alone, and this number increased to 50.6% in 2016. The key factors affecting treatment-seeking behavior were education level, wealth index, household size, and distance to hospitals. Our results indicated that gaps in malaria case management remain and out-of-policy treatment is still a concern.