Considerable uncertainty surrounds both the consequences of climate change and their valuation over horizons of decades or centuries. Yet, there have been few attempts to factor such uncertainty into current policy decisions concerning stringency and instrument choice. This paper presents a framework for determining optimal climate change policy under uncertainty and compares the resulting prescriptions to those derived from a more typical analysis with best-guess parameter values. Uncertainty raises the optimal level of emission reductions and leads to a preference for taxes over rate controls. The first effect is driven primarily by uncertainty about future discount rates while the second arises because of relatively linear damages and a negative correlation between control costs and damages. Importantly, the welfare gains associated with policies computed from best-guess parameter values are significantly less than those which take uncertainty into account - on the order of 30%. This suggests that analyses which ignore uncertainty lead to inefficient policy recommendations.