BACKGROUND: The evidence base for effects of nutritional interventions for malnourished HIV-infected patients starting antiretroviral therapy (ART) is limited and inconclusive. OBJECTIVE: We hypothesized that both vitamin and mineral deficiencies and poor appetite limit weight gain in malnourished patients starting ART and that vitamin and mineral supplementation would improve appetite and permit nutritional recovery. DESIGN: The randomized controlled Nutritional Support for Africans Starting Antiretroviral Therapy trial was conducted in Mwanza, Tanzania, and Lusaka, Zambia. ART-naive adults referred for ART and with body mass index <18.5 kg/m received lipid-based nutritional supplements either without (LNS) or with added vitamins and minerals (LNS-VM), beginning before ART initiation. Participants were given 30 g/d LNS from recruitment until 2 weeks after starting ART and 250 g/d from weeks 2 to 6 of ART. RESULTS: Of 1815 patients recruited, 365 (20%) died during the study and 813 (45%) provided data at 12 weeks. Controlling for baseline values, anthropometric measures were consistently higher at 12-week ART in the LNS-VM than in the LNS group but statistically significant only for calf and mid-upper arm circumferences and triceps skinfold. Appetite did not differ between groups. Using piecewise mixed-effects quadratic models including all patients and time points, the main effects of LNS-VM were seen after starting ART and were significant for weight, body mass index, and mid-upper arm circumference. CONCLUSIONS: Provision of high levels of vitamins and minerals to patients referred for ART, delivered with substantial macronutrients, increased nutritional recovery but did not seem to act through treatment group differences in appetite.