BACKGROUND: Primary health care is essential in improving and maintaining the health of populations. It has the potential to accelerate achievement of the Millennium Development Goals and fulfill the "Health for All" doctrine of the Alma-Ata Declaration. Understanding the performance of the health system from a geographic perspective is important for improved health planning and evidence-based policy development. The aims of this study were to measure geographical accessibility, model spatial coverage of the existing primary health facility network, estimate the number of primary health facilities working under capacity and the population underserved in the Western Province of Rwanda. METHODS: This study uses health facility, population and ancillary data for the Western Province of Rwanda. Three different travel scenarios utilized by the population to attend the nearest primary health facility were defined with a maximum travelling time of 60 minutes: Scenario 1--walking; Scenario 2--walking and cycling; and Scenario 3--walking and public transportation. Considering these scenarios, a raster surface of travel time between primary health facilities and population was developed. To model spatial coverage and estimate the number of primary health facilities working under capacity, the catchment area of each facility was calculated by taking into account population coverage capacity, the population distribution, the terrain topography and the travelling modes through the different land categories. RESULTS: Scenario 2 (walking and cycling) has the highest degree of geographical accessibility followed by Scenario 3 (walking and public transportation). The lowest level of accessibility can be observed in Scenario 1 (walking). The total population covered differs depending on the type of travel scenario. The existing primary health facility network covers only 26.6% of the population in Scenario 1. In Scenario 2, the use of a bicycle greatly increases the population being served to 58% of inhabitants. When considering Scenario 3, the total population served is 34.3%. CONCLUSIONS: Significant spatial variations in geographical accessibility and spatial coverage were observed across the three travel scenarios. The analysis demonstrates that regardless of which travel scenario is used, the majority of the population in the Western Province does not have access to the existing primary health facility network. Our findings also demonstrate the usefulness of GIS methods to leverage multiple datasets from different sources in a spatial framework to provide support to evidence-based planning and resource allocation decision-making in developing countries.