Objective: To examine the association between nutritional markers at initiation and during follow up in two different cohorts of HIV-infected adults initiating highly active antiretroviral therapy (HAART) in West Africa. Methods: The ATARAO study was a one year prospective study carried in Mali. It consisted of a sample of consecutive patients initiating HAART in one of four participating centers during that period. Data were collected at time of treatment initiation (baseline) and every 3 months thereafter. The ANRS 1290 study followed Senegalese patients recruited in similar conditions. Bivariate analyses were used to identify nutritional and immunological covariates of malnutrition at baseline. Longitudinal trajectories of body mass index, hemoglobin and albumin, and their associated factors, were evaluated using mixed linear models. Results: In ATARAO, 250 participants were retained for analyses; of which, 36% had a BMI < 18.5 kg/m2, nearly 60% were anemic and 47.4% hypoalbuminemic at time of treatment initiation. At baseline, low hemoglobin, hypoalbuminemia and low CD4 levels were associated with a BMI < 18.5 kg/m2. Similarly, low BMI, low albumin and low CD4 counts were linked to anemia; while, hypoalbuminemia was associated with low hemoglobin levels and CD4 counts. In ANRS, out of the 372 participants retained for analyses, 31% had a low BMI and almost 70% were anemic. At baseline, low BMI was associated with low hemoglobin levels and CD4 counts, while anemia was associated with low CD4 counts and female sex. While treatment contributed to early gains in BMI, hemoglobin and albumin in the first 6 months of treatment, initial improvements plateaued or subsided thereafter. Despite HAART, malnutrition persisted in both cohorts after one year, especially in those who were anemic, hypoalbuminemic or had a low BMI at baseline. Conclusion: In ATARAO and ANRS, malnutrition was common across all indicators (BMI, hemoglobin, albumin) and persisted despite treatment. Low BMI, anemia and hypoalbuminemia were associated with attrition, and with a deficient nutritional and immunological status at baseline, as well as during treatment. In spite of therapy, malnutrition is associated with negative clinical and treatment outcomes which suggests that HAART may not be sufficient to address co-existing nutritional deficiencies.