Potential interactions between food production and climate mitigation are explored for two situations in sub-Saharan Africa, where deforestation and land degradation overlap with hunger and poverty. Three agriculture intensification scenarios for supplying nitrogen to increase crop production (mineral fertilizer, herbaceous legume cover crops—green manures—and agroforestry—legume improved tree fallows) are compared to baseline food production, land requirements to meet basic caloric requirements, and greenhouse gas emissions. At low population densities and high land availability, food security and climate mitigation goals are met with all intensification scenarios, resulting in surplus crop area for reforestation. In contrast, for high population density and small farm sizes, attaining food security and reducing greenhouse gas emissions require mineral fertilizers to make land available for reforestation; green manure or improved tree fallows do not provide sufficient increases in yields to permit reforestation. Tree fallows sequester significant carbon on cropland, but green manures result in net carbon dioxide equivalent emissions because of nitrogen additions. Although these results are encouraging, agricultural intensification in sub-Saharan Africa with mineral fertilizers, green manures, or improved tree fallows will remain low without policies that address access, costs, and lack of incentives. Carbon financing for small-holder agriculture could increase the likelihood of success of Reducing Emissions from Deforestation and Forest Degradation in Developing Countries programs and climate change mitigation but also promote food security in the region.