While agreeing on the choice of an optimal investment decision is already difficult for any diverse group of actors, priorities, and world views, the presence of deep uncertainties further challenges the decision-making framework by questioning the robustness of all purportedly optimal solutions. This paper summarizes the additional uncertainty that is created by climate change, and reviews the tools that are available to project climate change (including downscaling techniques) and to assess and quantify the corresponding uncertainty. Assuming that climate change and other deep uncertainties cannot be eliminated over the short term (and probably even over the longer term), it then summarizes existing decision-making methodologies that are able to deal with climate-related uncertainty, namely cost-benefit analysis under uncertainty, cost-benefit analysis with real options, robust decision making, and climate informed decision analysis. It also provides examples of applications of these methodologies, highlighting their pros and cons and their domain of applicability. The paper concludes that it is impossible to define the "best" solution or to prescribe any particular methodology in general. Instead, a menu of methodologies is required, together with some indications on which strategies are most appropriate in which contexts. This analysis is based on a set of interviews with decision-makers, in particular World Bank project leaders, and on a literature review on decision-making under uncertainty. It aims at helping decision-makers identify which method is more appropriate in a given context, as a function of the project's lifetime, cost, and vulnerability.