Quality of service is of major economic significance in natural monopoly infrastructure industries but is generally not reflected in efficiency analysis. In this paper we present an efficiency analysis of electricity distribution networks using a sample of about 500 electricity distribution utilities from seven European countries. We apply the stochastic frontier analysis (SFA) method on multi-output translog input distance function models to estimate cost and scale efficiency with and without incorporating quality of service. We show that introducing the quality dimension into the analysis affects estimated efficiency significantly. In contrast to previous research, smaller utilities seem to indicate lower technical efficiency when incorporating quality. We also show that incorporating quality of service does not alter scale economy measures. Quality of service should be an integrated part of efficiency analysis and incentive regulation regimes, as well as in the economic review of market concentration in regulated natural monopolies.