Cereal residues represent a major resource for livestock feeding during the dry season in southern Africa. When kept on the soil surface instead of feeding them to livestock, crop residues can contribute to increasing soil fertility and maintaining crop productivity in the short- and the long-term. We explored these trade-offs for smallholder cotton–sorghum farming systems in the semi-arid Zambezi Valley, northern Zimbabwe. The analysis was done using simulation models at three scales, the plot, the farm and the territory, to simulate the effects of different sorghum residue allocations to livestock feeding vs. soil mulching, in combination with different application rates of mineral nitrogen fertilizer on crop productivity. The plot-scale simulations suggest that without N fertilization soil mulching has a positive effect on cotton yields only if small quantities of sorghum residues are used as mulch (average cotton yields of 2.24 ± 0.41 kg ha−1 with a mulch of 100 kg ha−1 vs. 1.91 ± 0.29 kg ha−1 without mulch). Greater quantities of mulch have a negative effect on cotton yield without N fertilization due to N immobilization in the soil microbial biomass. With applications of 100 kg N ha−1, quantities of mulch up to 3 t ha−1 have no negative effect on cotton yield. Results at farm-scale highlight the fundamental role of livestock as a source of traction, and the need to feed a greater proportion of sorghum residues to livestock as herd and farm sizes increase. Farmers with no livestock attained maximum crop production when 100% of their sorghum residue remained in the field, as they do not have access to cattle manure. The optimum fraction of crop residue to be retained in the fields for maximum farm crop production varied for farmers with 2 or less heads of cattle (80% retention), with 2–3 heads (60–80%), with 4 or more heads (40–60%). At the scale of the entire territory, total cotton and sorghum production increased with the density of cattle, at the expense of soil mulching with crop residues. The results of our simulations suggest that (i) the optimum level of residue retention depends on the scale at which trade-offs are analyzed; (ii) the retention of all of the crop residue as mulch appears unrealistic and undesirable in farming systems that rely on livestock for traction; and (iii) crop residue mulching could be made more attractive to farmers by paying due attention to balancing C to N ratios in the soil and by promoting small-scale mechanization to replace animal traction.