The individual impacts of several components of family planning service quality on contraceptive use have been studied, but the influence of a composite measure synthesizing these components has not been often investigated. We (1) develop a composite score for family planning service quality based on health facility data from Burkina Faso, Ethiopia, Kenya and Uganda and (2) examine the influence of structural quality on contraceptive practice in these four countries. We used nationally representative cross-sectional survey data of health facilities and women of reproductive age. First, we constructed quality scores for facilities using principal component analysis to integrate 18 variables. Second, we linked women to their closest facility using geo-coordinates. Third, we estimated multivariable logistic regression models to calculate women’s odds ratios for modern contraceptive use adjusting for facilities’ quality and other factors. In Burkina Faso, Ethiopia and Uganda, the odds of using a modern method of contraception was greater if the nearest facility provided high- or medium-quality services compared with low quality in the univariable model. After controlling for possible confounders, the adjusted odds ratios were significant for high quality (aOR: 3.12, P value: 0.005) and medium quality (aOR: 2.57, P value: 0.009) in Ethiopia and in the hypothesized direction but not statistically significant in Uganda or Burkina Faso, and in the opposite direction in Kenya. A process quality measure—having been visited by a community health worker—was statistically significantly associated with modern contraceptive use in three of the four countries (Burkina Faso aOR: 2.18, P value: 0.000; Ethiopia aOR: 1.78, P value: 0.000; Uganda aOR: 1.96, P value: 0.012). These results suggest that service quality in public facilities may be less relevant to contraceptive use in environments where the universe and reach of providers changes actively. Programs promoting contraception therefore need to consider quality within facility types and their service environments.