Land is a complex ecosystem that provides various ecosystem service functions that are necessary and important for the development of sustainable cities. For rapid urbanization and industrialization, considerable areas of eco-service land have been utilized for urban construction, resulting in serious ecological and environmental issues, such as deteriorated urban heat islands, soil erosion, air and water pollution, and decreased biodiversity, which seriously challenge the sustainable development capacity. The output of natural eco-service function is eco-efficiency, and it can be divided into positive and negative eco-services; positive eco-services could create the basis of harmony and a comfortable environment; however, negative eco-services could impede sustainable development. Urban land use and cover change are often responsible for increasing negative eco-services. To understand the process of how eco-service efficiency changes with the implementation of city master plans, this paper took Beijing as a case study based on GIS and RS technology, with the support of socioeconomic data, methods grid analyses, and complex ecological assessments, and established spatial indexes for a complex eco-efficiency assessment from both positive and negative aspects. The results showed that during the period from 2003 to 2011, when the last city master plan was being implemented, the negative eco-service efficiency of the urban land increased from 42.3% to 48.7%, and correspondingly, the positive eco-service efficiency decreased from 57.7% to 51.3%. In the last eight years, the center of Beijing City continued expanding outwards at the expense of eco-service lands, resulting in increasing negative eco-service efficiency. To create a livable and sustainable city, it was suggested that the Department of City Planning and Management should develop a strategic plan to effectively manage the city development, especially, to clearly determine the urban spatial structure. Furthermore, it is essential to strengthen the complex eco-service efficiency of the land by optimizing land use structure in urban and rural areas, and efficiently conserve the rural natural environment.