Abstract Background Low body mass index (BMI) individuals starting antiretroviral therapy (ART) for HIV infection in sub-Saharan Africa have high rates of death and loss to follow-up in the first 6 months of treatment. Nutritional supplementation may improve health outcomes in this population, but the anticipated benefit of any intervention should be commensurate with the cost given resource limitations and the need to expand access to ART in the region. Methods We used Markov models incorporating historical data and program-wide estimates of treatment costs and health benefits from the Zambian national ART program to estimate the improvements in 6-month survival and program retention among malnourished adults necessary for a combined nutrition support and ART treatment program to maintain cost-effectiveness parity with ART treatment alone. Patients were stratified according to World Health Organization criteria for severe (BMI <16.0 kg/m2), moderate (16.00-16.99 kg/m2), and mild (17.00-18.49 kg/m2) malnutrition categories. Results 19,247 patients contributed data between May 2004 and October 2010. Quarterly survival and retention were lowest in the BMI <16.0 kg/m2 category compared to higher BMI levels, and there was less variation in both measures across BMI strata after 180 days. ART treatment was estimated to cost $556 per year and averted 7.3 disability-adjusted life years. To maintain cost-effectiveness parity with ART alone, a supplement needed to cost $10.99 per quarter and confer a 20% reduction in both 6-month mortality and loss to follow-up among BMI <16.0 kg/m2 patients. Among BMI 17.00-18.49 kg/m2 patients, supplement costs accompanying a 20% reduction in mortality and loss to follow-up could not exceed $5.18 per quarter. In sensitivity analyses, the maximum permitted supplement cost increased if the ART program cost rose, and fell if patients classified as lost to follow-up at 6 months subsequently returned to care. Conclusions Low BMI adults starting ART in sub-Saharan Africa are at high risk of early mortality and loss to follow-up. The expense of providing nutrition supplementation would require only modest improvements in survival and program retention to be cost-effective for the most severely malnourished individuals starting ART, but interventions are unlikely to be cost-effective among those in higher BMI strata.