Nature-based Solutions (NbS) build synergies between biodiversity conservation and societal challenges such as climate change. This paper derives a working definition of NbS based on an evaluation of existing definitions, in particular the IUCN (2016) definition. It critically assesses the global mitigation potential of NbS in relevant studies for forests, croplands, grasslands, terrestrial and coastal wetlands as well as settlements. Recommendations for international climate policy are derived. The study finds that it is likely that NbS potentials provided by scientific literature overestimate the realistic potential of NbS for climate change mitigation. Nevertheless, NbS should be advanced as they involve a number of co-benefits. The success of NbS to mitigate climate change and deliver ecological and social co-benefits will very much depend on eliminating direct and indirect pressures on ecosystems caused by current patterns of production and consumption.