Health-related quality of life (HRQoL) is an important outcome measure among HIV-infected patients receiving combination antiretroviral therapy (cART), but has not been studied extensively in resource-limited settings. Insight in the predictors or correlates of poor HRQoL may be helpful to identify patients most in need of additional support and to design appropriate interventions. A cross-sectional study was conducted between September 2012 and April 2013 in 10 healthcare facilities in Addis Ababa, Ethiopia. Patients who were at least 6 months on cART were randomly selected and individual patient data were retrieved from medical records. HRQoL was measured by the WHOQoL-HIVBREF, depressive-symptoms by the Kessler-6 scale, and stigma by the Kalichman internalized AIDS-related stigma scale. Multivariate linear regression analysis was carried-out to examine associations between HRQoL and the other variables. A total of 664 patients (response-rate 95%) participated in the study. A higher level of depressive-symptoms was most strongly and consistently associated with a lower HRQoL, both in terms of the magnitude of the relationship and in the number of HRQoL domains associated with it. Also, a higher level of HIV-stigma was associated with a lower HRQoL except for the physical domain, while obtaining sufficient nutritious food and job opportunity were associated with a better HRQoL except for the spiritual and social domains, respectively. Demographics, clinical, and treatment characteristics yielded few significant associations with HRQoL. Our study findings suggest that interventions to improve HRQoL should focus on reducing depressive-symptoms and HIV-stigma, and on enhancing food security and job opportunity.