Malnourished HIV-infected patients starting antiretroviral therapy (ART) are at high risk of early mortality, some of which may be attributed to altered electrolyte metabolism. We used data from a randomised controlled trial of electrolyte-enriched lipid-based nutritional supplements to assess the association of baseline and time-varying serum phosphate and K concentrations with mortality within the first 12 weeks after starting ART. Baseline phosphate results were available from 1764 patients and there were 9096 subsequent serum phosphate measurements, a median of 6 per patient. For serum K there were 1701 baseline and 8773 subsequent measures, a median of 6 per patient. Abnormally high or low serum phosphate was more common than high or low serum K. Controlling for other factors found to affect mortality in this cohort, low phosphate which had not changed from the previous time interval was associated with increased mortality; the same was not true for high phosphate or for high or low K. Both increases and decreases in serum electrolytes from the previous time interval were generally associated with increased mortality, particularly in the electrolyte-supplemented group. The results suggest that changes in serum electrolytes, largely irrespective of the starting point and the direction of change, were more strongly associated with mortality than were absolute electrolyte levels. Although K and phosphate are required for tissue deposition during recovery from malnutrition, further studies are needed to determine whether specific supplements exacerbate physiologically adverse shifts in electrolyte levels during nutritional rehabilitation of ill malnourished HIV patients.