Due to a lack of evaluation of the implementation of water planning policies, based on long-term spatio-temporal analysis, this research uses Beijing as an empirical case study to bridge this gap. We analyze the spatio-temporal evolution of water problems and water planning implementations. Content analysis, cluster analysis, and spatial interpolation analysis are used to illustrate the spatio-temporal evolution of water planning implementation. In addition, a grey relational model is developed to determine the impact of the most relevant implementation objects on each water issue. The results indicate that the Beijing water crisis evolves from the center outwards in a planar expansion. However, the water plan implementation shows linear and point characteristics. The majority of implementation categories consist of single-function infrastructure. The implemented categories ‘which show a significant implementation peak’ influence more than one water issue. The categories ‘that were implemented at a steady rate’ have a high relational grade with both surface and underground water shortage problems. Different implementation types from different planning categories may have simultaneous effects on one kind of water problem. Thus, improving water governance is the key to water security in Beijing. This study may serve as a reference for future water planning in other cities.