Abstract: The world population is projected to increase to 9–10 billion by 2050, during which time it will be necessary to reduce anthropogenic greenhouse gas emissions to mitigate climate change. The particular challenge this places on agriculture is to identify practices which ensure stable and productive food supply that also have a low greenhouse gas (GHG) intensity. Maize is the principle staple crop in many parts of Africa with low and variable yields, averaging only 1.6 t/ha in sub-Saharan Africa (SSA). Food security and increasing crop yields are considered priorities in SSA over impacts of food production on GHG emissions. Here we describe an approach that can be used to inform a decision support tree for optimal interventions to obtain sufficient food production with low GHG intensity, and we demonstrate its applicability to SSA. We employed a derivative of the farm greenhouse gas calculator ‘Cool Farm Tool’ (CFT) on a large survey of Kenyan and Ethiopian smallholder maize-based systems in an assessment of GHG intensity. It was observed that GHG emissions are strongly correlated with nitrogen (N) input. Based on the relationship between yield and GHG emissions established in this study, a yield of 0.7 t/ha incurs the same emissions as those incurred for maize from newly exploited land for maize in the region. Thus, yields of at least 0.7 t/ha should be ensured to achieve GHG intensities lower than those for exploiting new land for production. Depending on family size, the maize yield required to support the average consumption of maize per household in these regions was determined to be between 0.3 and 2.0 t/ha, so that the desirable yield can be even higher from a food security perspective. Based on the response of the observed yield to increasing N application levels, average optimum N input levels were determined as 60 and 120 kg N/ha for Kenya and Ethiopia, respectively. Nitrogen balance calculations could be applied to other countries or scaled down to districts to quantify the trade-offs, and to optimise crop productivity and GHG emissions.