Lipid-based nutrient supplements (LNS) may be beneficial for malnourished HIV-infected patients starting antiretroviral therapy (ART). We assessed the effect of adding vitamins and minerals to LNS on body composition and handgrip strength during ART initiation. ART-eligible HIV-infected patients with BMI <18·5 kg/m2 were randomised to LNS or LNS with added high-dose vitamins and minerals (LNS-VM) from referral for ART to 6 weeks post-ART and followed up until 12 weeks. Body composition by bioelectrical impedance analysis (BIA), deuterium (2H) diluted water (D2O) and air displacement plethysmography (ADP), and handgrip strength were determined at baseline and at 6 and 12 weeks post-ART, and effects of LNS-VM v. LNS at 6 and 12 weeks investigated. BIA data were available for 1461, D2O data for 479, ADP data for 498 and handgrip strength data for 1752 patients. Fat mass tended to be lower, and fat-free mass correspondingly higher, by BIA than by ADP or D2O. At 6 weeks post-ART, LNS-VM led to a higher regain of BIA-assessed fat mass (0·4 (95 % CI 0·05, 0·8) kg), but not fat-free mass, and a borderline significant increase in handgrip strength (0·72 (95 % CI -0·03, 1·5) kg). These effects were not sustained at 12 weeks. Similar effects as for BIA were seen using ADP or D2O but no differences reached statistical significance. In conclusion, LNS-VM led to a higher regain of fat mass at 6 weeks and to a borderline significant beneficial effect on handgrip strength. Further research is needed to determine appropriate timing and supplement composition to optimise nutritional interventions in malnourished HIV patients.