Fatigue and depression are among the most frequently rated symptoms of people with HIV/AIDS. This study aimed: (1) to describe severity of fatigue and depression in an outpatient sample (n = 372) of men and women with HIV/AIDS, (2) to evaluate sensitivity and discriminant validity for two fatigue and three depression scales and (3) to investigate whether fatigue and depression are conceptually distinct concepts or reciprocally dependent. This was a secondary analysis of a descriptive, cross-sectional study with convenience sampling. Fatigue was assessed with the fatigue factor score of the revised Sign and Symptom Checklist HIV (SSC-HIVrev), and the fatigue scale of the Self-Care Symptom Management for Living with HIV/AIDS Scale 20(SCSMS-F). Depression was assessed with the depression factor score of the SSC-HIVrev, the depression scale of the SCSMC-D and the Center for Epidemiologic Studies Depression Scale (CES-D). Most of the participants were male (67%), with a mean age of 39.9 years, and of African American decent (73%). Dependent on the instrument, the average fatigue severity was moderate and the average depression severity was moderate to severe. Women experienced higher fatigue and depression severity scores than men. The scores on the same instruments for fatigue and depression showed significant correlations (SSC-HIVrev fatigue and depression r = 0.62; SCSMS fatigue and depression r = 0.64), indicating that both concepts are closely related. Patients seeking help for fatigue and/or depression should always be evaluated for both symptoms. Future research is needed to identify dimensions in different fatigue and depression scales in order to differentiate the impact of both symptoms on people living with HIV/AIDS.