Although various studies have shown that corn-ethanol reduces greenhouse gas (GHG) emissions by displacing fossil fuel use, many of these studies fail to include how land use history affects the net carbon balance through changes in soil carbon content. We evaluated the effectiveness and economic value of corn- and cellulosic-ethanol production for reducing net GHG emissions when produced on lands with different land-use histories, comparing these strategies with reductions achieved by set-aside programs such as the Conservation Reserve Program (CRP). Depending on prior land use, our analysis shows that C releases from the soil after planting corn for ethanol may in some cases completely offset C gains attributed to biofuel generation for at least 50 years. More surprisingly, based on our comprehensive analysis of 142 soil studies, soil C sequestered by setting aside former agricultural land was greater than the C credits generated by planting corn-ethanol on the same land for 40 years, and had equal or greater economic net present value. Once commercially available, cellulosic ethanol produced in set-aside grasslands should provide the most efficient tool for GHG reduction of any scenario we examined. Our results suggest that conversion of CRP lands or other set-aside programs to corn-ethanol production should not be encouraged through greenhouse gas policies.