Understanding the effects of payments on the adoption of reforestation in agricultural areas and the associated food-carbon trade-offs is necessary to inform climate change policy. Economic viability of reforestation under payment per hectare and payment per tonne schemes for carbon sequestration was assessed in a region in southern Australia supporting 6.1 Mha of rain-fed agriculture. The results show that under the median scenario, a carbon price of 27 A$/tCO2-e could make one-third of the study area (nearly 2 Mha) more profitable for reforestation than agriculture, and at 58 A$/tCO2-e all of the study area could become more profitable. The results were sensitive to variation in carbon risk factor, establishment costs, and discount rates. Pareto-optimal land allocation could realize one-third of the potential carbon sequestration from reforestation (16.35 MtCO2-e/yr at a carbon risk factor of 0.8) with a loss of less than one-tenth (107.89 A$M/yr) of the agricultural production. Both payment schemes resulted in efficiencies within 1% of the Pareto-optimum. Understanding food-carbon trade-offs and policy efficiencies can inform carbon policy design.