Background: In rhesus macaques, simian immunodeficiency virus infection is followed by expansion of enteric viruses but has a limited impact on the gut bacteriome. To understand the longitudinal effects of HIV-1 infection on the human gut microbiota, we prospectively followed 49 Mozambican subjects diagnosed with recent HIV-1 infection (RHI) and 54 HIV-1-negative controls for 9–18 months and compared them with 98 chronically HIV-1- infected subjects treated with antiretrovirals (n = 27) or not (n = 71). Results: We show that RHI is followed by increased fecal adenovirus shedding, which persists during chronic HIV-1 infection and does not resolve with ART. Recent HIV-1 infection is also followed by transient non-HIV-specific changes in the gut bacterial richness and composition. Despite early resilience to change, an HIV-1-specific signature in the gut bacteriome—featuring depletion of Akkermansia, Anaerovibrio, Bifidobacterium, and Clostridium—previously associated with chronic inflammation, CD8+ T cell anergy, and metabolic disorders, can be eventually identified in chronically HIV-1-infected subjects. Conclusions: Recent HIV-1 infection is associated with increased fecal shedding of eukaryotic viruses, transient loss of bacterial taxonomic richness, and long-term reductions in microbial gene richness. An HIV-1-associated microbiome signature only becomes evident in chronically HIV-1-infected subjects.