Objectively evaluating the spatio-temporal changes in regional eco-environmental quality is an important basis for ecological environmental protection and sustainable development. This paper presents a first attempt to develop a prototype framework that can assess eco-environmental quality from the aspect of landscape structure and ecosystem function. We constructed a general index with which to describe and compare the eco-environmental quality status of two important river basins around Beijing over the past 30 years. The assessment of this study confirmed that the eco-environmental quality in the Daqing River Fuping basin and the Luanhe River Shandianhe basin has changed significantly, with obvious spatial disparity and temporal differences. There were different factors influencing the ecoenvironmental quality in the two regions, but the changes in forest land and grassland area and their associated service functions, as a result of human activities, were the main influencing factors in both basins. The developed framework reflected the spatio-temporal changes in regional eco-environmental quality of the two basins from 1985 to 2015. The evaluation of the framework can provide a reference for the ecological planning of the areas around Beijing. Specifically, this framework can be replicated on different spatial and temporal scales and can represent a new approach for the evaluation of eco-environmental quality in other regions.