Interrelationships between urban and rural areas are fundamental for the development and safeguarding of viable future living conditions and quality of life. These areas are not well-delineated or self-sufficient, and existing interrelations may privilege one over the other. Major urban challenges facing China and Europe are related to changes in climate, environment, and to decision-making that makes urban and rural landscapes more susceptible to environmental pressures. Focusing on the six European and Chinese cities and surrounding rural areas, under study in the joint EC and MOST-funded REGREEN project, we examine how nature-based solutions (NBS) may assist in counteracting these pressures. We explore urban-rural dependencies and partnerships regarding NBS that can enhance resilience in Europe and China. We analyse differences between European and Chinese systems of governance, reflecting on the significance of the scale of research needed to understand how NBS provide benefits. We highlight interactions between differently delineated sheds (watershed, airshed, natureshed, and peopleshed), which influence the interrelationships between urban and rural areas. There may be one-way or two-way interdependence, and the impact may be uni or multi-directional. The European and Chinese solutions, exemplified in this article, tackle the nexus of environmental and peoplesheds. We discuss complex human interactions (and how to model them) that may, or may not, lead to viable and equitable partnerships for implementing NBS in cities within Europe and in China. © 2022 by the authors. Licensee MDPI, Basel, Switzerland.