Quality of service (QoS) is of major economic significance in natural monopoly infrastructure industries. In this article, we present an efficiency analysis of electricity distribution networks from seven European countries. We apply the stochastic frontier analysis method to multi-output translog input distance function models to estimate cost efficiency and scale economies. We show that introducing the quality dimension into the analysis affects estimated efficiency significantly, especially that smaller utilities’ efficiency seems to decrease. Our results emphasize that QoS should be an integrated part of efficiency and economic analysis of regulated natural monopolies.