BACKGROUND: Assessment of physical access to health services is extremely important for planning. Complex methods that incorporate data inputs from road networks and transport systems are used to assess physical access to healthcare in industrialised countries. However, such data inputs hardly exist in many developing countries. Straight-line distances between the service provider and resident population are easily obtained but their relationship with driving distance and travel time is unclear. This study aimed to investigate the relationship between different measures of physical access, including straight-line distances, road distances and travel time and the impact of these measures on the vaccination of children in Yemen. METHODS: Coordinates of houses and health facilities were determined by GPS machine in Urban and rural areas in Taiz province, Yemen. Road distances were measured by an odometer of a vehicle driven from participants' houses to the nearest health centre. Driving time was measured using a stop-watch. Data on children's vaccination were collected by personal interview and verified by inspecting vaccination cards. RESULTS: There was a strong correlation between straight-line distances, driving distances and driving time (straight line distances vs. driving distance r = 0.92, p < 0.001, straight line distances vs. driving time r = 0.75; p < 0.001, driving distance vs. driving time r = 0.83, p < 0.001). Each measure of physical accessibility showed strong association with vaccination of children after adjusting for socio-economic status. CONCLUSION: Straight-line distances, driving distances and driving time are strongly linked and associated with vaccination uptake. Straight-line distances can be used to assess physical access to health services where data inputs on road networks and transport are lacking. Impact of physical access is clear in Yemen, highlighting the need for efforts to target vaccination and other preventive healthcare measures to children who live away from health facilities.