World agriculture needs to find the right balance to cope with the trilemma between feeding a growing population, reducing its impact on biodiversity and minimizing greenhouse gas (GHG) emissions. In this paper, we evaluate a broad range of scenarios that achieve 4.3 GtCO_2,eq/year GHG mitigation in the Agriculture, Forestry and Other Land-Use (AFOLU) sector by 2100. Scenarios include varying mixes of three GHG mitigation policies: second-generation biofuel production, dietary change and reforestation of pasture. We find that focusing mitigation on a single policy can lead to positive results for a single indicator of food security or biodiversity conservation, but with significant negative side effects on others. A balanced portfolio of all three mitigation policies, while not optimal for any single criterion, minimizes trade-offs by avoiding large negative effects on food security and biodiversity conservation. At the regional scale, the trade-off seen globally between biodiversity and food security is nuanced by different regional contexts.