While climate change is widely regarded as a threat to food security in southern Africa, few studies attempt to link the science of climate change impacts on agriculture with the specificities of smallholder livelihoods. In this paper, we build a series of linear programming (LP) farm-household models in Zambia in order to assess the impact of climate change on rural households and likely changes in land use and crop management. The LP models represent three household types (smallholders, emergent farmers, and female-headed households) in three agro-ecological zones with divergent cropping patterns and climate trends. Model parameters are drawn from several nationally representative rural household surveys, local meteorological records, and downscaled climate predictions of the Hadley (HadCM3) and CCSM models for the year 2050. The calorie-maximizing LP models are calibrated to best reflect baseline crop distributions at each site. Statistical analyses of crop yields over nine years reveal that crops in Zambia exhibit varying levels of sensitivity to climate shocks, and under climate change scenarios, the LP models indicate that farmers will shift their choices of technologies and crops. Among smallholder farms, calorie production from field crops changes by -13.56 to +5.13% under the Hadley predictions and -10.61 to +9.79% under the CCSM predictions. Although farm-households are expected to meet their consumption requirements even under climate change scenarios, the probability of falling below a minimum threshold of calorie production increases in two of our three study sites, and this is particularly true for smallholder farmers who face binding land constraints. Given the current choice set, autonomous on-farm adaptation generally will not be enough to offset the negative yield effects of climate change. Zambia therefore needs larger-scale institutional developments and agricultural research to provide farmers with additional adaptation options.