We estimate and map the impacts that alternative national and subnational economic incentive structures for reducing emissions from deforestation (REDD+) in Indonesia would have had on greenhouse gas emissions and national and local revenue if they had been in place from 2000 to 2005. The impact of carbon payments on deforestation is calibrated econometrically from the pattern of observed deforestation and spatial variation in the benefits and costs of converting land to agriculture over that time period. We estimate that at an international carbon price of $10/tCO2e, a “mandatory incentive structure,” such as a cap-and-trade or symmetric tax-and-subsidy program, would have reduced emissions by 163–247 MtCO2e/y (20–31% below the without-REDD+ reference scenario), while generating a programmatic budget surplus. In contrast, a “basic voluntary incentive structure” modeled after a standard payment-for-environmental-services program would have reduced emissions nationally by only 45–76 MtCO2e/y (6–9%), while generating a programmatic budget shortfall. By making four policy improvements—paying for net emission reductions at the scale of an entire district rather than site-by-site; paying for reductions relative to reference levels that match business-as-usual levels; sharing a portion of district-level revenues with the national government; and sharing a portion of the national government's responsibility for costs with districts—an “improved voluntary incentive structure” would have been nearly as effective as a mandatory incentive structure, reducing emissions by 136–207 MtCO2e/y (17–26%) and generating a programmatic budget surplus.