BACKGROUND: A substantial proportion of HIV-infected adults starting antiretroviral therapy (ART) in sub-Saharan Africa are malnourished. We aimed to increase understanding of the factors affecting their high mortality, particularly in the high-risk period before ART initiation. METHODS: We analysed potential risk factors for mortality of Zambian and Tanzanian participants enrolled in the NUSTART clinical trial. Malnourished adults (n = 1815; body mass index [BMI] <18.5 kg/m2) were recruited at referral to ART and randomised to receive different nutritional supplements. Demographics, measures of body composition, blood electrolytes and clinical conditions were investigated as potential risk factors using Poisson regression models. RESULTS: The mortality rate was higher in the period from referral to starting ART (121 deaths/100 person-years; 95 % CI 103, 142) than during the first 12 weeks of ART (66; 95 % CI 57, 76) and was not affected by trial study arm. In adjusted analyses, lower CD4 count, BMI and mid-arm circumference and raised C-reactive protein were associated with an increased risk of mortality throughout the study. Male sex and lower hand-grip strength carried an increased risk in the pre-ART period. Participants on tuberculosis treatment at referral had a lower mortality rate (adjusted Rate Ratio 0.44; 95 % CI 0.31, 0.63). CONCLUSION: Among malnourished ART-eligible adults, pre-ART mortality was twice that in the early post-ART period, suggesting many early ART deaths represent advanced HIV disease rather than treatment-related events. Therefore, more efforts are needed to promote earlier diagnosis and immediate initiation of ART, as recently recommended by WHO for all persons with HIV worldwide. The positive effect of tuberculosis treatment suggests undiagnosed tuberculosis is a contributor to mortality in this population. TRIAL REGISTRATION: Pan African Clinical Trials Registry, PACTR201106000300631 ; registered on 1st June 2011.