Fatigue is the most commonly noted symptom among people living with human immunodeficiency virus (PLHIV). The aim of this study was to investigate the prevalence and predictors of fatigue among PLHIV in Norway. Two hundred and forty-four people were recruited from two hospitals to participate in a survey, which contained seven instruments used to investigate mental health, addiction, quality of life, and fatigue. More than a third of the participants (38.5%) suffered from fatigue. Predictors of fatigue were the presence of mental distress (adjusted odds ratio AOR 8.98, 95%CI 3.81, 21.15), multimorbidity (AOR 5.13, 95%CI 1.40, 18.73), living alone (AOR 2.99, 95%CI 1.36, 6.56), trouble sleeping (AOR 2.67, 95%CI 1.06, 6.71), and increased body pain (AOR 1.44, 95%CI 1.25, 1.67). To improve the quality of life for many PLHIV, the continuum of HIV care must address fatigue and its predictors.