Abstract Background Most Ministries of Health across Africa invest substantial resources in some form of health management information system (HMIS) to coordinate the routine acquisition and compilation of monthly treatment and attendance records from health facilities nationwide. Despite the expense of these systems, poor data coverage means they are rarely, if ever, used to generate reliable evidence for decision makers. One critical weakness across Africa is the current lack of capacity to effectively monitor patterns of service use through time so that the impacts of changes in policy or service delivery can be evaluated. Here, we present a new approach that, for the first time, allows national changes in health service use during a time of major health policy change to be tracked reliably using imperfect data from a national HMIS. Methods Monthly attendance records were obtained from the Kenyan HMIS for 1 271 government-run and 402 faith-based outpatient facilities nationwide between 1996 and 2004. A space-time geostatistical model was used to compensate for the large proportion of missing records caused by non-reporting health facilities, allowing robust estimation of monthly and annual use of services by outpatients during this period. Results We were able to reconstruct robust time series of mean levels of outpatient utilisation of health facilities at the national level and for all six major provinces in Kenya. These plots revealed reliably for the first time a period of steady nationwide decline in the use of health facilities in Kenya between 1996 and 2002, followed by a dramatic increase from 2003. This pattern was consistent across different causes of attendance and was observed independently in each province. Conclusion The methodological approach presented can compensate for missing records in health information systems to provide robust estimates of national patterns of outpatient service use. This represents the first such use of HMIS data and contributes to the resurrection of these hugely expensive but underused systems as national monitoring tools. Applying this approach to Kenya has yielded output with immediate potential to enhance the capacity of decision makers in monitoring nationwide patterns of service use and assessing the impact of changes in health policy and service delivery.