Waste management in the big cities of Indonesia is still become a complicated problem. This article aims to analyze the influence of socio-economic factors which consist of GRDP per capita, population density, gender ratio, the proportion of population productive age and education on the efficiency of waste management service (WMS) in provincial capitals in Indonesia. The method used was Stochastic Frontier Analysis (SFA). The resulted WMS efficiency from this study were 0.39. Based on that value, it means the efficiency of WMS are still low and the efficiency can be improved about 61%. It also can be concluded that all variables were significantly influenced the WMS efficiency, except gender ratio. Expected that the result of this study can be used by both central and local government to improve the WMS in Indonesia.