Fatigue and depression are common co-morbid conditions among people with HIV infection. We analyzed a population of HIV-infected adults with depression, who were enrolled in a depression treatment trial, to examine the extent to which improvements in depression over time were associated with improvements in HIV-related fatigue. Data for this analysis come from a randomized controlled trial to evaluate the effectiveness of improved depression treatment on antiretroviral adherence. Fatigue was measured using the HIV-Related Fatigue Scale, and depressive symptoms were measured with the Hamilton Depression Rating Scale. Participants (n = 234) were on average nearly 44 years of age and predominantly male, black or African American, and unemployed. Individuals who experienced stronger depression response (i.e., greater improvement in depression score) had larger decreases in fatigue. However, even among those who demonstrated a full depression response, nearly three-quarters continued to have either moderate or severe fatigue at 6 and 12 months.