HIV infection is considered a scenario of accelerated aging. Previous studies have suggested a link between aging, frailty, and gut dysbiosis, but there is a knowledge gap regarding the HIV population. Our objective was to compare the fecal bacteriome of older people with HIV (PWH) and non-HIV controls, and to assess potential links between gut dysbiosis and frailty. A total of 36 fecal samples (24 from PWH and 12 from non-HIV controls) were submitted to a metataxonomic analysis targeting the V3–V4 hypervariable region of the 16S rRNA gene. High-quality reads were assembled and classified into operational taxonomic units. Alpha diversity, assessed using the Shannon index, was higher in the control group than in the HIV group (p Blautia was higher in the HIV group (p Blautia was also higher in PWH with depression (p = 0.004), whereas the opposite was observed for the genus Bifidobacterium (p = 0.004). Our study shows shifts in the composition of the PWH bacteriome when compared to that of healthy controls. To our knowledge, this is the first study suggesting a potential link between depression and gut dysbiosis in the HIV population.