Rapidly rising populations and likely increases in incomes in sub-Saharan Africa make tens of millions of hectares of cropland expansion nearly inevitable, even with large increases in crop yields. Much of that expansion is likely to occur in higher rainfall savannas, with substantial costs to biodiversity and carbon storage. Zambia presents an acute example of this challenge, with an expected tripling of population by 2050, good potential to expand maize and soya bean production, and large areas of relatively undisturbed miombo woodland and associated habitat types of high biodiversity value. Here, we present a new model designed to explore the potential for targeting agricultural expansion in ways that achieve quantitatively optimal trade-offs between competing economic and environmental objectives: total converted land area (the reciprocal of potential yield); carbon loss, biodiversity loss and transportation costs. To allow different interests to find potential compromises, users can apply varying weights to examine the effects of their subjective preferences on the spatial allocation of new cropland and its costs. We find that small compromises from the objective to convert the highest yielding areas permit large savings in transportation costs, and the carbon and biodiversity impacts resulting from savannah conversion. For example, transferring just 30% of weight from a yield-maximizing objective equally between carbon and biodiversity protection objectives would increase total cropland area by just 2.7%, but result in avoided costs of 27–47% for carbon, biodiversity and transportation. Compromise solutions tend to focus agricultural expansion along existing transportation corridors and in already disturbed areas. Used appropriately, this type of model could help countries find agricultural expansion alternatives and related infrastructure and land use policies that help achieve production targets while helping to conserve Africa’s rapidly transforming savannahs.