Urban-rural nature-based solutions (NBS) have co-benefits for water availability, water quality, and flood management. Searching for optimal integrated urban-rural NBS planning to maximise these co-benefits is important for catchment scale water management. This study develops an integrated urban-rural NBS planning optimisation framework. In this framework, the CatchWat-SD model is developed to simulate a multi-catchment integrated water cycle in the Norfolk region, UK. Three rural (runoff attenuation features, regenerative farming, floodplain) and two urban (urban green space, constructed wastewater wetlands) NBS interventions are integrated into the model at a range of implementation scales. A many-objective optimization problem with seven water management objectives to account for flow, quality and cost indicators is formulated, and the NSGAII algorithm is adopted to search for optimal NBS portfolios. Results show that rural NBS have more significant impacts across the catchment, which increase with the scale of implementation. Integrated urban-rural NBS planning can improve water availability, water quality, and flood management simultaneously, though trade-offs exist between different objectives. Runoff attenuation features and floodplains provide the greatest benefits for water availability. While regenerative farming is most effective for water quality and flood management, though it decreases water availability by up to 15% because it retains more water in the soil. Phosphorus levls are best reduced by expansion of urban green space to decrease loading on combined sewer systems, though this trades off against water availability, flood, nitrogen and suspended solids. The proposed framework enables spatial prioritisation of NBS, which may ultimately guide multi-stakeholder decision-making.