Gut microbiota dysbiosis features progressive HIV infection and is a potential target for intervention. Herein, we explored the microbiome of 16 elite controllers (EC), 32 antiretroviral therapy naive progressors and 16 HIV negative controls. We found that the number of observed genera and richness indices in fecal microbiota were significantly higher in EC versus naive. Genera Succinivibrio, Sutterella, Rhizobium, Delftia, Anaerofilum and Oscillospira were more abundant in EC, whereas Blautia and Anaerostipes were depleted. Additionally, carbohydrate metabolism and secondary bile acid synthesis pathway related genes were less represented in EC. Conversely, fatty acid metabolism, PPAR-signalling and lipid biosynthesis proteins pathways were enriched in EC vs naive. The kynurenine pathway of tryptophan metabolism was altered during progressive HIV infection, and inversely associated with microbiota richness. In conclusion, EC have richer gut microbiota than untreated HIV patients, with unique bacterial signatures and a distinct metabolic profile which may contribute to control of HIV.