Urbanization is considered one of the current main drivers of climate change and loss of biodiversity, which are strongly interconnected. Nature-based Solutions (NbS) can be used to reduce and manage the negative effects of human activities in cities by improving local environmental quality and reducing the risks related to environmental degradation, but they need to be planned and designed with the support of meaningful data to ensure and quantify their contribution. This paper proposes a conceptual framework to computationally quantify the performance of NbS in relation to its capacity to improve adaptation to and mitigation of climate change, and to support local biodiversity from a holistic environmentally sustainable perspective. This methodological framework relies on the identification of Key Performance Indicators (KPIs) which can be used to quantify the effects of a design solution on the main environmental risks related to climate change and biodiversity loss. For the selected KPIs, identified as the most impactful and relevant regarding the environmental hazards, a computational approach is proposed to set the ground for the design optimization of specific NBS for a specific site with specific needs.