The HIV/AIDS pandemic threatens economic, social, and environmental sustainability throughout sub-Saharan Africa. This paper reports on a qualitative study exploring interrelationships between HIV/AIDS, labor availability, agricultural productivity, household resources, food consumption, and health status in rural southeastern Uganda. Respondents reported an increase in widow-and-orphan-headed households; labor shortages due to illness and caretaking; degradation of household resources from health-related expenses; loss of land tenure and assets following deaths, especially for widows and orphans; and changes in agricultural practices and productivity. Our study highlights a potential downward spiral of livelihood degradation for vulnerable households and suggests targeted interventions to improve sustainability.