Abstract Background The central sexual health centre (SHC) in the greater Rotterdam area in the Netherlands helps finding people unaware of their STI/HIV status. We aimed to determine a possible association between SHC utilization and travel distance in this urban and infrastructure-rich area. Insight in area-specific utilization helps adjust outreach policies to enhance STI testing. Methods The study population consists of all residents aged 15–45 years in the greater Rotterdam area (2015–17). We linked SHC consultation data from STI tested heterosexual clients to the population registry. The association between SHC utilization and distance was investigated by multilevel modelling, adjusting for sociodemographic and area-specific determinants. The data were also stratified by age (aged < 25 years) and migratory background (non-Western), since SHC triage may affect their utilization. We used straight-line distance between postal code area centroid and SHC address as a proxy for travel distance. Results We found large area variation in SHC utilization (range: 1.13–48.76 per 1000 residents). Both individual- and area-level determinants determine utilization. Travel distance explained most area variation and was inversely associated with SHC utilization when adjusted for other sociodemographic and area-specific determinants [odds ratio (OR) per kilometre: 0.95; 95% confidence interval (CI): 0.93–0.96]. Similar results were obtained for residents <25 years (OR: 0.95; 95% CI: 0.94–0.96), but not for non-Western residents (OR: 0.99; 95% CI: 0.99–1.00). Conclusions Living further away from a central SHC shows a distance decline effect in utilization. We recommend to enhance STI testing by offering STI testing services closer to the population.