Agriculture faces three great challenges: feeding a growing population, reducing its impact on biodiversity and minimizing greenhouse gas (GHG) emissions. Therefore, it is important to assess synergies and trade-offs in meeting these challenges. In this paper, we evaluate a broad range of scenarios that achieve 4.3 GtCO2/year GHG mitigation in the Agriculture, Forestry and Other Land-Use (AFOLU) sector by 2100. Scenarios include varying mixes of three GHG mitigation policies: biofuel crop production, dietary change and reforestation of pasture. We evaluated the impacts of these scenarios on food security and biodiversity conservation. We find that focusing mitigation on a single policy can lead to positive results for one indicator, but with significant negative side effects on others. For example, mitigation dominated by reforestation favors biodiversity criteria, but is projected to lead to sharp increases in food prices. Mitigation scenarios focusing on biofuels have strong adverse effects on both biodiversity and food security indicators. 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 projected impact of mitigation policies are similar to proection at global scale, except for Canada and Middle-East. Due to the small area of agricultural land in these regions, their average regional levels of biodiversity are mainly influenced by the state of their natural areas and not by agricultural land-use changes.