BACKGROUND: Malnourished HIV-infected African adults are at high risk of early mortality after starting antiretroviral therapy (ART). We hypothesized that short-course, high-dose vitamin and mineral supplementation in lipid nutritional supplements would decrease mortality. METHODS: The study was an individually-randomised phase III trial conducted in ART clinics in Mwanza, Tanzania, and Lusaka, Zambia. Participants were 1,815 ART-naïve non-pregnant adults with body mass index (BMI) <18.5 kg/m² who were referred for ART based on CD4 count <350 cells/μL or WHO stage 3 or 4 disease. The intervention was a lipid-based nutritional supplement either without (LNS) or with additional vitamins and minerals (LNS-VM), beginning prior to ART initiation; supplement amounts were 30 g/day (150 kcal) from recruitment until 2 weeks after starting ART and 250 g/day (1,400 kcal) from weeks 2 to 6 after starting ART. The primary outcome was mortality between recruitment and 12 weeks of ART. Secondary outcomes were serious adverse events (SAEs) and abnormal electrolytes throughout, and BMI and CD4 count at 12 weeks ART. RESULTS: Follow-up for the primary outcome was 91%. Median adherence was 66%. There were 181 deaths in the LNS group (83.7/100 person-years) and 184 (82.6/100 person-years) in the LNS-VM group (rate ratio (RR), 0.99; 95% CI, 0.80-1.21; P = 0.89). The intervention did not affect SAEs or BMI, but decreased the incidence of low serum phosphate (RR, 0.73; 95% CI, 0.55-0.97; P = 0.03) and increased the incidence of high serum potassium (RR, 1.60; 95% CI, 1.19-2.15; P = 0.002) and phosphate (RR, 1.23; 95% CI, 1.10-1.37; P <0.001). Mean CD4 count at 12 weeks post-ART was 25 cells/μL (95% CI, 4-46) higher in the LNS-VM compared to the LNS arm (P = 0.02). CONCLUSIONS: High-dose vitamin and mineral supplementation in LNS, compared to LNS alone, did not decrease mortality or clinical SAEs in malnourished African adults initiating ART, but improved CD4 count. The higher frequency of elevated serum potassium and phosphate levels suggests high-level electrolyte supplementation for all patients is inadvisable but the addition of micronutrient supplements to ART may provide clinical benefits in these patients. TRIAL REGISTRATION: PACTR201106000300631, registered on 1st June 2011.