Physical access to health care affects a large array of health outcomes, yet meaningfully estimating physical access remains elusive in many developing country contexts where conventional geographical techniques are often not appropriate. We interviewed (and geographically positioned) 23,000 homesteads regarding clinic usage in the Hlabisa health sub-district, KwaZulu-Natal, South Africa. We used a cost analysis within a geographical information system to estimate mean travel time (at any given location) to clinic and to derive the clinic catchments. The model takes into account the proportion of people likely to be using public transport (as a function of estimated walking time to clinic), the quality and distribution of the road network and natural barriers, and was calibrated using reported travel times. We used the model to investigate differences in rural, urban and peri-urban usage of clinics by homesteads in the study area and to quantify the effect of physical access to clinic on usage. We were able to predict the reported clinic used with an accuracy of 91%. The median travel time to nearest clinic is 81 min and 65% of homesteads travel 1h or more to attend the nearest clinic. There was a significant logistic decline in usage with increasing travel time (p < 0.0001). The adjusted odds of a homestead within 30 min of a clinic making use of the clinics were 10 times (adjusted OR = 10; 95 CI 6.9-14.4) those of a homestead in the 90-120 min zone. The adjusted odds of usage of the clinics by urban homesteads were approximately 20/30 times smaller than those of their rural/peri-urban counterparts, respectively, after controlling for systematic differences in travel time to clinic. The estimated median travel time to the district hospital is 170 min. The methodology constitutes a framework for modelling physical access to clinics in many developing country settings.