Urban flooding has become a serious issue in most Chinese cities due to rapid urbanization and extreme weather, as evidenced by severe events in Beijing (2012), Ningbo (2013), Guangzhou (2015), Wuhan (2016), Shenzhen (2019), and Chongqing (2020). The Chinese “Sponge City Program” (SCP), initiated in 2013 and adopted by 30 pilot cities, is developing solutions to manage urban flood risk, purify stormwater, and provide water storage opportunities for future usage. Emerging challenges to the continued implementation of Sponge Cities include (1) uncertainty regarding future hydrological conditions related to climate change projections, which complicates urban planning and designing infrastructure that will be fit for purpose over its intended operating life, and (2) the competing priorities of stakeholders and their reluctance to make trade-offs, which obstruct future investment in the SCP. Nature-Based Solutions (NBS) is an umbrella concept that emerged from Europe, which encourages the holistic idea of considering wider options that combine “Blue–Green” practices with traditional engineering to deliver “integrated systems of Blue–Green–Grey infrastructure”. NBS includes interventions making use of natural processes and ecosystem services for functional purposes, and this could help to improve current pilot SCP practices. This manuscript reviews the development of the SCP, focusing on its construction and design aspects, and discusses how approaches using NBS could be included in the SCP to tackle not only urban water challenges but also a wide range of social and environmental challenges, including human health, pollution (via nutrients, metals, sediments, plastics, etc.), flood risk, and biodiversity.