The global total amount of generated solid waste is currently on a rapid growth trend. China, as the largest developing country, promulgated its Pilot Work Plan for the Construction of Zero-Waste Cities led by the new development concept in 2018 after recognizing the inadequacy and urgency of solid waste management, and the lack of valuable experience and benchmark cities for the construction of zero-waste cities. This study uses the undesirable super-efficiency model and kernel density estimation method to measure the efficiency of zero-waste city construction in 16 prefecture-level cities in Shandong Province and analyze their spatial and temporal differences. Three major problems were found, namely, low regional coordination, the rigid policies of some local governments, and the unbalanced development of scale efficiency and pure technical efficiency. Results show that the zero-waste city construction efficiency as a whole shows a declining and then fluctuating growth trend, and that low-scale efficiency is the main reason behind the decrease in construction efficiency. Suggestions are then provided considering three aspects: improving regional synergy; improving government quality and capacity, and strengthening government supervision and revitalizing the market; and introducing social capital for environmental pollution treatment. These suggestions ultimately help improve the level of zero-waste city construction.