The Energy Market Regulatory Authority (EMRA) sets the tariff that determines the revenue requirements of the Turkish natural gas distribution companies by using a popular type of an incentive regulation, the price cap method. Generally, incentive regulation improves efficiency and reduces costs; on the other hand the companies may not be willing to increase the service quality in this kind of regulation. This chapter analyzes the efficiency and service quality of the Turkish natural gas distribution companies. The findings should also be of interest to regulators in other developing countries that are at the early stage of their natural gas market regulation. The companies' efficiency scores are evaluated both by non-parametric and parametric methods, Data Envelopment Analysis (DEA) and Stochastic Frontier Analysis (SFA) respectively. The same distribution companies are ranked by the service quality scores that are obtained from service quality data. The results are used to determine the relationship between efficiency and service quality of the companies, to decide on the effectiveness of the regulation and to suggest a reward/penalty scheme for the tariff design.