To address challenges associated with climate resilience, health and well-being in urban areas, current policy platforms are shifting their focus from ecosystem-based to nature-based solutions (NBS), broadly defined as solutions to societal challenges that are inspired and supported by nature. NBS result in the provision of co-benefits, such as the improvement of place attractiveness, of health and quality of life, and creation of green jobs. Few frameworks exist for acknowledging and assessing the value of such co-benefits of NBS and to guide cross-sectoral project and policy design and implementation. In this paper, we firstly developed a holistic framework for assessing co-benefits (and costs) of NBS across elements of socio-cultural and socio-economic systems, biodiversity, ecosystems and climate. The framework was guided by a review of over 1700 documents from science and practice within and across 10 societal challenges relevant to cities globally. We found that NBS can have environmental, social and economic co-benefits and/or costs both within and across these 10 societal challenges. On that base, we develop and propose a seven-stage process for situating co-benefit assessment within policy and project implementation. The seven stages include: 1) identify problem or opportunity; 2) select and assess NBS and related actions; 3) design NBS implementation processes; 4) implement NBS; 5) frequently engage stakeholders and communicate co-benefits; 6) transfer and upscale NBS; and 7) monitor and evaluate co-benefits across all stages. We conclude that the developed framework together with the seven-stage co-benefit assessment process represent a valuable tool for guiding thinking and identifying the multiple values of NBS implementation.