Human immunodeficiency virus (HIV) infection is associated with increased intestinal translocation of microbial products and enteropathy as well as alterations in gut bacterial communities. However, whether the enteric virome contributes to this infection and resulting immunodeficiency remains unknown. We characterized the enteric virome and bacterial microbiome in a cohort of Ugandan patients, including HIV-uninfected or HIV-infected subjects and those either treated with anti-retroviral therapy (ART) or untreated. Low peripheral CD4 T cell counts were associated with an expansion of enteric adenovirus sequences and this increase was independent of ART treatment. Additionally, the enteric bacterial microbiome of patients with lower CD4 T counts exhibited reduced phylogenetic diversity and richness with specific bacteria showing differential abundance, including increases in Enterobacteriaceae, which have been associated with inflammation. Thus, immunodeficiency in progressive HIV infection is associated with alterations in the enteric virome and bacterial microbiome, which may contribute to AIDS-associated enteropathy and disease progression.