Nearly a decade after the adoption of confirmed diagnosis and artemisinin combination therapy (ACT) for the treatment of uncomplicated falciparum malaria, a large treatment gap persists. We describe a novel approach of combining data from households and the universe of treatment sources in their vicinities to produce nationally representative indicators of physical and financial access to malaria care from the household's perspective in Benin, Nigeria, Uganda and Zambia. We compare differences in access across urban and rural areas, countries, and over time. In 2009, more urban households had a provider stocking ACT within 5 km than rural households. By 2012, this physical ACT access gap had largely been closed in Uganda, and progress had been made in Benin and Nigeria; but the gap persisted in Zambia. The private sector helped to fill this gap in rural areas. Improvements in Nigeria and Uganda were driven largely by increased ACT availability in licensed drug stores, and in Benin by increased availability in unregulated open-air market stalls. Free or subsidised ACT from public and non-profit facilities continued to be available to many households by 2012, but much less so in rural areas. Where private sector expansion increased physical access to ACT, these additional options were on average more expensive. Also by 2012, the majority of urban households in all four countries had access to a provider nearby offering malaria diagnostic services; however, this access remained low for rural households in Benin, Nigeria and Zambia. The methods developed in this study could improve how access to healthcare is measured in low- and middle-income country settings, particularly where private for-profit providers are an important source of care, and for conditions that may be treated by informal providers. The method could also lead to better explanations of the performance of complex interventions aiming to improve healthcare access.